結果
問題 | No.2804 Fixer And Ratism |
ユーザー |
|
提出日時 | 2024-07-12 21:19:42 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 3,950 bytes |
コンパイル時間 | 4,157 ms |
コンパイル使用メモリ | 279,708 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-12 21:19:50 |
合計ジャッジ時間 | 6,219 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/modint>using namespace atcoder;#ifdef DEFINED_ONLY_IN_LOCAL#include <dump.hpp>#define dump(...) cpp_dump(__VA_ARGS__)#else#undef dump#define dump(...)#endif#define rep1(i, a) for (int i = 0; i < (int)(a); i++)#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); i++)#define rep3(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))#define overloadRep(a, b, c, d, e, ...) e#define rep(...) overloadRep(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)#define rrep(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)#define drep(i, a, b) for (int i = (int)(a); i >= (int)(b); i--)#define all(a) a.begin(), a.end()#define rall(a) a.rbegin(), a.rend()using ll = long long;using ull = unsigned long long;const int inf = 1e9;const ll INF = 1e18;const int dx[4] = {0, 1, 0, -1};const int dy[4] = {1, 0, -1, 0};const int ddx[8] = {1, 0, -1, 0, 1, -1, 1, -1};const int ddy[8] = {0, 1, 0, -1, 1, -1, -1, 1};struct cincout {cincout() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout << fixed << setprecision(15);}} init;// chmax chmintemplate <class T>inline bool chmax(T &a, T b) {if (a < b) {a = b;return true;}return false;}template <class T>inline bool chmin(T &a, T b) {if (a > b) {a = b;return true;}return false;}// pairtemplate <class T1, class T2>istream &operator>>(istream &is, pair<T1, T2> &p) {is >> p.first >> p.second;return is;}template <class T1, class T2>ostream &operator<<(ostream &os, const pair<T1, T2> &p) {os << p.first << " " << p.second << '\n';return os;}// vectortemplate <class T>istream &operator>>(istream &is, vector<T> &v) {for (T &in : v) {is >> in;}return is;}template <class T>ostream &operator<<(ostream &os, const vector<T> &v) {rep(i, (int)v.size()) {os << v[i] << " \n"[i + 1 == (int)v.size()];}return os;}template <class T>istream &operator>>(istream &is, vector<vector<T>> &vv) {for (vector<T> &v : vv) {is >> v;}return is;}template <class T>ostream &operator<<(ostream &os, vector<vector<T>> &vv) {for (vector<T> &v : vv) {os << v;}return os;}// bitbool bit(ll x, int p) {return (x >> p) & 1;}// grid outbool out(int ni, int nj, int h, int w) {return (ni < 0 or ni >= h or nj < 0 or nj >= w);}// popcountint pc(ll x) {return __builtin_popcountll(x);}// max(vector)template <class T>T max(vector<T> x) {return *max_element(x.begin(), x.end());}using P=pair<int,string>;int main(){int n,q;cin>>n>>q;set<P>st;map<string,int>mp;int p=n;vector<string>ans;while(q--){int t;cin>>t;//dump(st);if(t==1){string s;int r;cin>>s>>r;mp[s]=r;st.emplace(r,s);if(st.size()>p){ans.push_back(st.begin()->second);st.erase(st.begin());}}else if(t==2){int x;cin>>x;p-=x;vector<P>cur;while(st.size()>p){string s=st.begin()->second;if(mp[s]>=10000){cur.emplace_back(mp[s]-10000,s);}else{cur.emplace_back(mp[s],s);}st.erase(st.begin());}sort(all(cur));rep(i,cur.size())ans.push_back(cur[i].second);}else{string s;int x;cin>>s>>x;p+=x;if(mp[s]<=9999){st.erase(P(mp[s],s));mp[s]+=10000;st.emplace(mp[s],s);}}}rep(i,ans.size())cout<<ans[i]<<endl;return 0;}