結果

問題 No.449 ゆきこーだーの雨と雪 (4)
ユーザー hashiryo
提出日時 2019-06-27 19:23:03
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

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