結果
問題 |
No.449 ゆきこーだーの雨と雪 (4)
|
ユーザー |
![]() |
提出日時 | 2018-11-13 18:18:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 955 ms / 5,000 ms |
コード長 | 2,348 bytes |
コンパイル時間 | 3,218 ms |
コンパイル使用メモリ | 228,312 KB |
最終ジャッジ日時 | 2025-01-06 16:36:01 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#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; }