結果
問題 | No.1705 Mode of long array |
ユーザー |
![]() |
提出日時 | 2021-09-19 14:31:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 616 ms / 3,000 ms |
コード長 | 3,208 bytes |
コンパイル時間 | 1,833 ms |
コンパイル使用メモリ | 120,120 KB |
最終ジャッジ日時 | 2025-01-24 15:51:08 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include <iostream> #include <vector> #include <unordered_map> #include <set> #include <algorithm> #include <utility> using namespace std; using ll=long long; struct Queries{ ll T,X,Y; }; class Mode{ private: unordered_map<ll,ll> place; vector<ll> count; vector<set<ll>> S; multiset<ll> max_S; public: Mode(ll M,unordered_map<ll,ll>& um,vector<ll>& A){ place=um; S.resize(um.size()); count.resize(M,0); for(ll i=0;i<M;i++){ // i が A[i] 個ある max_S.insert(0); add(i,A.at(i)); //max_S.insert(place.at(A.at(i))); //cerr<<"insert max_S: "<<A.at(i)<<" "<<place.at(A.at(i))<<endl; //cerr<<"init add: "<<i<<" "<<A.at(i)<<endl; } } void add(ll x,ll y){ // x:0-indexed ll now=count.at(x); //cerr<<"x: "<<x<<", y: "<<y<<", now: "<<now<<endl; S.at(place.at(now)).erase(x); max_S.erase(max_S.find(place.at(now))); //cerr<<"erase max_S: "<<now<<" "<<place.at(now)<<endl; S.at(place.at(now+y)).insert(x); max_S.insert(place.at(now+y)); //cerr<<"insert max_S: "<<now+y<<" "<<place.at(now+y)<<endl; count.at(x)+=y; } void erase(ll x,ll y){ ll now=count.at(x); S.at(place.at(now)).erase(x); max_S.erase(max_S.find(place.at(now))); //cerr<<"erase max_S: "<<now<<" "<<place.at(now)<<endl; S.at(place.at(now-y)).insert(x); max_S.insert(place.at(now-y)); //cerr<<"insert max_S: "<<now-y<<" "<<place.at(now-y)<<endl; count.at(x)-=y; } ll get(){ //cerr<<"get"<<endl; ll max_place=*max_S.rbegin(); //cerr<<"max_place: "<<max_place<<endl; return *S.at(max_place).rbegin()+1; } void debug_conut(){ for(ll i=0;i<count.size();i++){ cerr<<count.at(i)<<" "; } cerr<<endl; } void debug_max_S(){ cerr<<"max_S: "; for(ll i:max_S){ cerr<<i<<" "; } cerr<<endl; } }; int main(){ ll N,M; cin>>N>>M; vector<ll> a(M); for(ll i=0;i<M;i++){ cin>>a.at(i); } vector<ll> b=a; ll Q; cin>>Q; vector<Queries> query(Q); // クエリ先読みして座圧する for(ll i=0;i<Q;i++){ cin>>query.at(i).T>>query.at(i).X>>query.at(i).Y; if(query.at(i).T==1){ b.push_back(b.at(query.at(i).X-1)); b.at(query.at(i).X-1)+=query.at(i).Y; }else if(query.at(i).T==2){ b.push_back(b.at(query.at(i).X-1)); b.at(query.at(i).X-1)-=query.at(i).Y; } } b.push_back(0); sort(b.begin(),b.end()); //cerr<<"sort end"<<endl; unordered_map<ll,ll> place; place.insert(make_pair(b.at(0),0)); ll cnt=1; //cerr<<"place: 0 "; for(ll i=1;i<b.size();i++){ if(b.at(i-1)!=b.at(i)){ //cerr<<b.at(i)<<" "; place.insert(make_pair(b.at(i),cnt)); cnt++; } } //cerr<<endl; Mode mode(M,place,a); //cerr<<"query start"<<endl; for(ll i=0;i<Q;i++){ //mode.debug_max_S(); if(query.at(i).T==1){ mode.add(query.at(i).X-1,query.at(i).Y); }else if(query.at(i).T==2){ mode.erase(query.at(i).X-1,query.at(i).Y); }else{ cout<<mode.get()<<endl; } //cerr<<"i: "<<i<<" end"<<endl; } return 0; }