結果
問題 | No.449 ゆきこーだーの雨と雪 (4) |
ユーザー | hashiryo |
提出日時 | 2019-06-27 19:23:03 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 314 ms / 5,000 ms |
コード長 | 4,077 bytes |
コンパイル時間 | 2,140 ms |
コンパイル使用メモリ | 190,616 KB |
実行使用メモリ | 54,832 KB |
最終ジャッジ日時 | 2023-10-23 16:11:41 |
合計ジャッジ時間 | 13,007 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 15 ms
44,008 KB |
testcase_01 | AC | 15 ms
44,008 KB |
testcase_02 | AC | 15 ms
44,008 KB |
testcase_03 | AC | 18 ms
44,008 KB |
testcase_04 | AC | 16 ms
44,008 KB |
testcase_05 | AC | 16 ms
44,008 KB |
testcase_06 | AC | 15 ms
44,008 KB |
testcase_07 | AC | 16 ms
44,008 KB |
testcase_08 | AC | 17 ms
44,008 KB |
testcase_09 | AC | 16 ms
44,008 KB |
testcase_10 | AC | 17 ms
44,008 KB |
testcase_11 | AC | 16 ms
44,008 KB |
testcase_12 | AC | 243 ms
44,332 KB |
testcase_13 | AC | 314 ms
46,972 KB |
testcase_14 | AC | 277 ms
46,972 KB |
testcase_15 | AC | 307 ms
46,972 KB |
testcase_16 | AC | 288 ms
46,972 KB |
testcase_17 | AC | 294 ms
46,972 KB |
testcase_18 | AC | 244 ms
44,332 KB |
testcase_19 | AC | 268 ms
46,972 KB |
testcase_20 | AC | 266 ms
46,972 KB |
testcase_21 | AC | 289 ms
46,972 KB |
testcase_22 | AC | 294 ms
46,972 KB |
testcase_23 | AC | 238 ms
44,332 KB |
testcase_24 | AC | 277 ms
46,972 KB |
testcase_25 | AC | 234 ms
44,332 KB |
testcase_26 | AC | 230 ms
44,332 KB |
testcase_27 | AC | 290 ms
46,972 KB |
testcase_28 | AC | 280 ms
46,972 KB |
testcase_29 | AC | 265 ms
46,972 KB |
testcase_30 | AC | 289 ms
46,972 KB |
testcase_31 | AC | 291 ms
46,972 KB |
testcase_32 | AC | 267 ms
46,972 KB |
testcase_33 | AC | 278 ms
46,972 KB |
testcase_34 | AC | 234 ms
44,332 KB |
testcase_35 | AC | 301 ms
46,972 KB |
testcase_36 | AC | 238 ms
44,332 KB |
testcase_37 | AC | 178 ms
54,832 KB |
testcase_38 | AC | 220 ms
49,288 KB |
testcase_39 | AC | 168 ms
49,288 KB |
testcase_40 | AC | 167 ms
49,288 KB |
testcase_41 | AC | 243 ms
49,288 KB |
testcase_42 | AC | 192 ms
49,288 KB |
testcase_43 | AC | 143 ms
44,008 KB |
testcase_44 | AC | 88 ms
44,332 KB |
testcase_45 | AC | 115 ms
54,832 KB |
ソースコード
#include<bits/stdc++.h> #define debug(x) cerr << #x << ": " << x << endl #define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << endl using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<ll> vll; const ll INF = LLONG_MAX/2; const ll MOD = 1e9+7; const double EPS=1e-12; template<typename T> class multisetRBST{ private: unsigned xor128() { static unsigned x = 123456789, y = 362436069, z = 521288629, w = 88675123; unsigned t = x ^ (x << 11); x = y; y = z; z = w; return w = w ^ (w >> 19) ^ (t ^ (t >> 8)); } struct Node{ Node *l,*r; size_t cnt; T val; Node():cnt(0){l=r=nullptr;} Node(T val): cnt(1),val(val){l=r=nullptr;} }; const size_t LIM = 1e6; vector<Node> pool; size_t ptr; Node *root; T id; inline Node* create(){ return &pool[ptr++]; } inline Node* create(T v){ return &(pool[ptr++]=Node(v)); } inline size_t size(const Node* a){ if(a==nullptr) return 0; return a->cnt; } inline Node* update(Node* a){ if(a==nullptr) return a; a->cnt=size(a->l)+size(a->r)+1; return a; } Node* merge(Node* a,Node* b){ if(a==nullptr) return b; if(b==nullptr) return a; if(xor128()%(size(a)+size(b))<size(a)){ a->r=merge(a->r,b); return update(a); } b->l=merge(a,b->l); return update(b); } pair<Node*, Node*> split(Node* a,size_t k){ if(a==nullptr) return make_pair(a,a); if(k<=size(a->l)){ auto s=split(a->l,k); a->l=s.second; return make_pair(s.first,update(a)); } auto s=split(a->r,k-(size(a->l)+1)); a->r=s.first; return make_pair(update(a),s.second); } inline size_t lower_bound(Node *a,T v){ if(!a) return 0; if(v<=a->val)return lower_bound(a->l,v); else return size(a->l)+lower_bound(a->r,v)+1; } inline size_t upper_bound(Node *a,T v){ if(!a) return 0; if(v<a->val)return upper_bound(a->l,v); else return size(a->l)+upper_bound(a->r,v)+1; } inline T get(Node *a,size_t k){ if(!a) return id; if(k == size(a->l)) return a->val; if(k < size(a->l)) return get(a->l,k); else return get(a->r,k-size(a->l)-1); } public: multisetRBST(T id_):pool(LIM),ptr(0),root(nullptr),id(id_){} inline void insert(T v){ Node* b=create(v); auto s=split(root,lower_bound(v)); root=merge(merge(s.first,b),s.second); } inline void erase(T v){ assert(count(v)>0); auto s=split(root,lower_bound(v)); auto t=split(s.second,1); root=merge(s.first,t.second); } inline size_t lower_bound(T v){ return lower_bound(root,v); } inline size_t upper_bound(T v){ return upper_bound(root,v); } inline size_t count(T v){ return upper_bound(v)-lower_bound(v); } inline T kth_elment(size_t k){ return get(root,k); } }; int id(string name){ static int cnt=0; static map<string,int> mp; if(mp.count(name)==0){ mp[name]=cnt++; return cnt-1; }else{ return mp[name]; } } signed main(){ cin.tie(0); ios::sync_with_stdio(false); ll N;cin>>N; ll L[N]; for(ll i=0;i<N;i++)cin>>L[i]; ll score[100010]={}; ll lastup[100010]={}; ll ac[N]={}; ll T;cin>>T; multisetRBST<pair<ll,ll> > S({-INF,-INF}); for(ll t=1;t<=T;t++){ string Name;char P;cin>>Name>>P; ll idx=id(Name); if(P=='?'){ //debug(S.size()); cout<<S.lower_bound({-score[idx],lastup[idx]})+1<<endl; }else{ //debug(lastup[idx]); //debug(idx); if(lastup[idx]>0)S.erase({-score[idx],lastup[idx]}); score[idx]+=50*L[P-'A']+50*L[P-'A']*10/(8+2*++ac[P-'A']); lastup[idx]=t; S.insert({-score[idx],lastup[idx]}); } } return 0; }