結果
問題 | No.449 ゆきこーだーの雨と雪 (4) |
ユーザー | beet |
提出日時 | 2018-11-13 18:18:27 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 765 ms / 5,000 ms |
コード長 | 2,348 bytes |
コンパイル時間 | 3,008 ms |
コンパイル使用メモリ | 240,056 KB |
実行使用メモリ | 38,976 KB |
最終ジャッジ日時 | 2024-09-22 10:35:22 |
合計ジャッジ時間 | 20,021 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 4 ms
6,940 KB |
testcase_04 | AC | 4 ms
6,940 KB |
testcase_05 | AC | 4 ms
6,940 KB |
testcase_06 | AC | 3 ms
6,948 KB |
testcase_07 | AC | 3 ms
6,940 KB |
testcase_08 | AC | 3 ms
6,940 KB |
testcase_09 | AC | 3 ms
6,944 KB |
testcase_10 | AC | 4 ms
6,944 KB |
testcase_11 | AC | 3 ms
6,944 KB |
testcase_12 | AC | 329 ms
15,540 KB |
testcase_13 | AC | 461 ms
20,348 KB |
testcase_14 | AC | 460 ms
20,340 KB |
testcase_15 | AC | 450 ms
20,736 KB |
testcase_16 | AC | 458 ms
20,060 KB |
testcase_17 | AC | 473 ms
20,336 KB |
testcase_18 | AC | 327 ms
15,100 KB |
testcase_19 | AC | 463 ms
20,152 KB |
testcase_20 | AC | 448 ms
20,168 KB |
testcase_21 | AC | 461 ms
20,092 KB |
testcase_22 | AC | 465 ms
20,352 KB |
testcase_23 | AC | 334 ms
14,712 KB |
testcase_24 | AC | 489 ms
20,224 KB |
testcase_25 | AC | 347 ms
14,732 KB |
testcase_26 | AC | 347 ms
14,524 KB |
testcase_27 | AC | 466 ms
20,428 KB |
testcase_28 | AC | 460 ms
20,380 KB |
testcase_29 | AC | 460 ms
20,200 KB |
testcase_30 | AC | 461 ms
20,284 KB |
testcase_31 | AC | 463 ms
20,280 KB |
testcase_32 | AC | 454 ms
20,392 KB |
testcase_33 | AC | 462 ms
20,748 KB |
testcase_34 | AC | 341 ms
14,572 KB |
testcase_35 | AC | 460 ms
20,380 KB |
testcase_36 | AC | 352 ms
14,708 KB |
testcase_37 | AC | 765 ms
38,956 KB |
testcase_38 | AC | 566 ms
27,976 KB |
testcase_39 | AC | 450 ms
28,020 KB |
testcase_40 | AC | 462 ms
28,876 KB |
testcase_41 | AC | 570 ms
28,160 KB |
testcase_42 | AC | 552 ms
28,032 KB |
testcase_43 | AC | 293 ms
17,520 KB |
testcase_44 | AC | 239 ms
17,852 KB |
testcase_45 | AC | 437 ms
38,976 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template<typename T> struct BIT{ Int n; vector<T> bit; //1-indexed BIT():n(-1){} BIT(Int n_,T d):n(n_),bit(n_+1,d){} T sum(Int i){ T s=bit[0]; for(Int x=i;x>0;x-=(x&-x)) s+=bit[x]; return s; } void add(Int i,T a){ if(i==0) return; for(Int x=i;x<=n;x+=(x&-x)) bit[x]+=a; } Int lower_bound(Int w){ if(w<=0) return 0; Int x=0,r=1; while(r<n) r<<=1; for(Int k=r;k>0;k>>=1){ if(x+k<=n&&bit[x+k]<w){ w-=bit[x+k]; x+=k; } } return x+1; } T sum0(Int i){ return sum(i+1); } void add0(Int i,T a){ add(i+1,a); } T query(Int l,Int r){ return sum(r-1)-sum(l-1); } T query0(Int l,Int r){ return sum(r)-sum(l); } }; template<typename T> vector<T> compress(vector<T> v){ sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); return v; } template<typename T> map<T, Int> dict(const vector<T> &v){ map<T, Int> res; for(Int i=0;i<(Int)v.size();i++) res[v[i]]=i; return res; } //INSERT ABOVE HERE signed main(){ int n; cin>>n; vector<int> l(n); for(int i=0;i<n;i++) cin>>l[i]; vector<int> cnt(n,0); auto sc=[&](int x){return 50*l[x]+(500*l[x]/(8+2*++cnt[x]));}; int q; cin>>q; vector<string> ss; vector<char> ps; map<string, int> lst,sum; using P = pair<int, int>; vector<P> vp; for(int i=0;i<q;i++){ string s; char p; cin>>s>>p; if(isalpha(p)){ lst[s]=i; sum[s]+=sc(p-'A'); } vp.emplace_back(-sum[s],i); ss.emplace_back(s); ps.emplace_back(p); } vp.emplace_back(0,0); vp.emplace_back(1e9,-1); vp=compress(vp); auto dc=dict(vp); int m=lst.size(); BIT<int> bit(vp.size(),0); bit.add0(dc[P(0,0)],m); cnt.assign(n,0); lst.clear(); sum.clear(); for(int i=0;i<q;i++){ string s=ss[i]; char p=ps[i]; int &val=sum[s]; if(isalpha(p)){ bit.add0(dc[P(-val,lst[s])],-1); lst[s]=i; val+=sc(p-'A'); bit.add0(dc[P(-val,lst[s])],1); }else{ cout<<bit.sum0(dc[P(-val,lst[s])])<<endl; } } return 0; }