結果
問題 | No.449 ゆきこーだーの雨と雪 (4) |
ユーザー |
|
提出日時 | 2016-11-19 00:00:48 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 203 ms / 5,000 ms |
コード長 | 1,548 bytes |
コンパイル時間 | 1,894 ms |
コンパイル使用メモリ | 179,408 KB |
実行使用メモリ | 32,156 KB |
最終ジャッジ日時 | 2024-09-22 10:15:16 |
合計ジャッジ時間 | 9,453 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define F first #define S second typedef long long ll; typedef pair<ll,ll> P; typedef pair<ll,P> PP; ll bit[500010]; class BIT{ public: ll n; BIT(){fill(bit,bit+500010,0);} void add(ll i,ll x){ while(i<=n){ bit[i]+=x; i+=i&-i; } } ll sum(ll i){ ll s=0; while(i>0){ s+=bit[i]; i-=i&-i; } return s; } }; bool cmp(PP a, PP b) { if(a.F==b.F) return a.S.F<b.S.F; return a.F>b.F; } P p[111111]; ll d[111111]; vector<PP> a; vector<ll> c[111111]; ll b[111111]; int main() { ios::sync_with_stdio(0);cin.tie(0); ll n,m; cin >> n; int aa[n],bb[n]; for(int i=0;i<n;i++) cin >> aa[i]; cin >> m; memset(bb,0,sizeof(bb)); map<string,int> mm;ll k=0; for(int i=0; i<m; i++) { string s; char c; ll x,y; cin >> s >> c; if(!mm.count(s)) { mm[s]=k; k++; } x=mm[s]; if(c=='?') y=-1; else { y=c-'A'; bb[y]++; int z=50*aa[y]+50*aa[y]/(0.8+0.2*bb[y]); d[x]+=z; a.push_back(PP(d[x],P(i,x))); } p[i]=P(y,x); } for(int i=0; i<k; i++) a.push_back(PP(0,P(-1,i))); BIT t=BIT(); t.n=a.size(); sort(a.begin(),a.end(),cmp); for(int i=a.size()-1; i>=0; i--) c[a[i].S.S].push_back(i+1); for(int i=0; i<k; i++) { t.add(c[i][b[i]],1); b[i]++; } for(int i=0; i<m; i++) { ll x=p[i].S; if(p[i].F>=0) { t.add(c[x][b[x]-1],-1); t.add(c[x][b[x]],1); b[x]++; } else cout << t.sum(c[x][b[x]-1]) << endl; } return 0; }