This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0343 #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../vector/compress.cpp" #include "../../datastructure/binaryindexedtree.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; int n,c; cin>>n>>c; vector<int> ts(c),is(c),ps(c); for(int i=0;i<c;i++){ cin>>ts[i]>>is[i]; if(ts[i]==0) cin>>ps[i],is[i]--; } vector<ll> ss(n,0); using P = pair<ll, int>; vector<P> vp; for(int i=0;i<n;i++) vp.emplace_back(-ss[i],i); for(int i=0;i<c;i++){ if(ts[i]==0){ ss[is[i]]+=ps[i]; vp.emplace_back(-ss[is[i]],is[i]); } } vp=compress(vp); auto dc=dict(vp); BIT<int> bit(vp.size()); fill(ss.begin(),ss.end(),0); for(int i=0;i<n;i++) bit.add(dc[P(-ss[i],i)],+1); for(int i=0;i<c;i++){ if(ts[i]==0){ bit.add(dc[P(-ss[is[i]],is[i])],-1); ss[is[i]]+=ps[i]; bit.add(dc[P(-ss[is[i]],is[i])],+1); } if(ts[i]==1){ int k=bit.lower_bound(is[i])-1; cout<<vp[k].second+1<<' '<<-vp[k].first<<'\n'; } } return 0; }
#line 1 "test/aoj/0343.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0343 #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "vector/compress.cpp" #line 3 "vector/compress.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename V> V compress(V vs){ sort(vs.begin(),vs.end()); vs.erase(unique(vs.begin(),vs.end()),vs.end()); return vs; } template<typename T> map<T, int> dict(const vector<T> &vs){ map<T, int> res; for(int i=0;i<(int)vs.size();i++) res[vs[i]]=i; return res; } map<char, int> dict(const string &s){ return dict(vector<char>(s.begin(),s.end())); } template<typename T> vector<T> compressed(vector<T> vs){ auto dc=dict(compress(vs)); for(auto &v:vs) v=dc[v]; return vs; } //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 1 "datastructure/binaryindexedtree.cpp" #line 3 "datastructure/binaryindexedtree.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T> class BIT{ private: // \sum_{j < i} v[j] T sum(int i){ T s(0); for(int x=i;x>0;x-=(x&-x)) s+=bit[x]; return s; } public: int n; vector<T> bit; BIT(int n_):n(n_+1),bit(n_+2,0){} // v[i] += a void add(int i,T a){ for(int x=++i;x<=n;x+=(x&-x)) bit[x]+=a; } // \sum_{l <= i < r} v[i] T query(int l,int r){return sum(r)-sum(l);} // min({x | sum(x) >= w}) int lower_bound(const T w){ if(w<=0) return 0; T r=w; int x=0,p=1; while(p<n) p<<=1; for(int k=p;k>0;k>>=1){ if(x+k<=n and bit[x+k]<r){ r-=bit[x+k]; x+=k; } } x++; assert(sum(x-1)<w and sum(x)>=w); return x; } // min({x | sum(x) > w}) int upper_bound(T w){return lower_bound(w+1);} }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 9 "test/aoj/0343.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; int n,c; cin>>n>>c; vector<int> ts(c),is(c),ps(c); for(int i=0;i<c;i++){ cin>>ts[i]>>is[i]; if(ts[i]==0) cin>>ps[i],is[i]--; } vector<ll> ss(n,0); using P = pair<ll, int>; vector<P> vp; for(int i=0;i<n;i++) vp.emplace_back(-ss[i],i); for(int i=0;i<c;i++){ if(ts[i]==0){ ss[is[i]]+=ps[i]; vp.emplace_back(-ss[is[i]],is[i]); } } vp=compress(vp); auto dc=dict(vp); BIT<int> bit(vp.size()); fill(ss.begin(),ss.end(),0); for(int i=0;i<n;i++) bit.add(dc[P(-ss[i],i)],+1); for(int i=0;i<c;i++){ if(ts[i]==0){ bit.add(dc[P(-ss[is[i]],is[i])],-1); ss[is[i]]+=ps[i]; bit.add(dc[P(-ss[is[i]],is[i])],+1); } if(ts[i]==1){ int k=bit.lower_bound(is[i])-1; cout<<vp[k].second+1<<' '<<-vp[k].first<<'\n'; } } return 0; }