結果

問題 No.449 ゆきこーだーの雨と雪 (4)
ユーザー hashiryohashiryo
提出日時 2019-06-27 19:23:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 304 ms / 5,000 ms
コード長 4,077 bytes
コンパイル時間 2,432 ms
コンパイル使用メモリ 190,488 KB
実行使用メモリ 54,776 KB
最終ジャッジ日時 2024-09-22 10:36:03
合計ジャッジ時間 12,646 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 15 ms
43,976 KB
testcase_01 AC 16 ms
43,852 KB
testcase_02 AC 14 ms
43,824 KB
testcase_03 AC 17 ms
43,800 KB
testcase_04 AC 16 ms
43,924 KB
testcase_05 AC 17 ms
43,840 KB
testcase_06 AC 16 ms
43,968 KB
testcase_07 AC 16 ms
43,832 KB
testcase_08 AC 16 ms
43,828 KB
testcase_09 AC 16 ms
43,888 KB
testcase_10 AC 16 ms
43,932 KB
testcase_11 AC 16 ms
43,832 KB
testcase_12 AC 242 ms
43,988 KB
testcase_13 AC 275 ms
46,924 KB
testcase_14 AC 273 ms
46,768 KB
testcase_15 AC 288 ms
46,900 KB
testcase_16 AC 267 ms
46,812 KB
testcase_17 AC 271 ms
46,948 KB
testcase_18 AC 242 ms
44,192 KB
testcase_19 AC 262 ms
46,876 KB
testcase_20 AC 261 ms
46,812 KB
testcase_21 AC 280 ms
46,812 KB
testcase_22 AC 293 ms
46,868 KB
testcase_23 AC 247 ms
44,200 KB
testcase_24 AC 278 ms
46,788 KB
testcase_25 AC 237 ms
44,128 KB
testcase_26 AC 230 ms
44,048 KB
testcase_27 AC 282 ms
46,832 KB
testcase_28 AC 283 ms
46,876 KB
testcase_29 AC 266 ms
46,832 KB
testcase_30 AC 295 ms
46,784 KB
testcase_31 AC 286 ms
46,952 KB
testcase_32 AC 266 ms
46,836 KB
testcase_33 AC 269 ms
46,840 KB
testcase_34 AC 235 ms
44,104 KB
testcase_35 AC 304 ms
46,896 KB
testcase_36 AC 239 ms
44,120 KB
testcase_37 AC 173 ms
54,776 KB
testcase_38 AC 214 ms
49,284 KB
testcase_39 AC 170 ms
49,272 KB
testcase_40 AC 169 ms
49,360 KB
testcase_41 AC 248 ms
49,400 KB
testcase_42 AC 198 ms
49,284 KB
testcase_43 AC 141 ms
44,048 KB
testcase_44 AC 87 ms
44,184 KB
testcase_45 AC 114 ms
54,736 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0