結果

問題 No.449 ゆきこーだーの雨と雪 (4)
ユーザー rickytheta
提出日時 2016-11-18 23:04:32
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 235 ms / 5,000 ms
コード長 4,583 bytes
コンパイル時間 1,932 ms
コンパイル使用メモリ 178,584 KB
実行使用メモリ 19,716 KB
最終ジャッジ日時 2024-09-22 09:35:03
合計ジャッジ時間 10,553 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:166:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  166 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
main.cpp:167:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  167 |   REP(i,n)scanf("%d",a+i);
      |           ~~~~~^~~~~~~~~~
main.cpp:171:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  171 |   scanf("%d",&t);
      |   ~~~~~^~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

bool lsss(int x,int y);

struct Treap{
private:
  static const ll rd_msk = (1ll<<32)-1;
  static ll rd(){
    static ll rd_x = 123456789;
    static ll rd_y = 362436069;
    static ll rd_z = 521288629;
    static ll rd_w = 88675123;
    ll t = (rd_x^(rd_x<<11))&rd_msk;
    rd_x = rd_y;
    rd_y = rd_z;
    rd_z = rd_w;
    return rd_w = (rd_w^(rd_w>>19)) ^ (t^(t>>8));
  }
  struct node{
    ll val,pri,cnt;;
    node *lch, *rch;
    node(ll val):val(val),cnt(1){
      pri = rd();
      lch = rch = NULL;
    }
  };
public:
  node *root;
  Treap():root(NULL){}
private:
  ll count(node *t){return t==NULL?0:t->cnt;}
  node* update(node *t){t->cnt=count(t->lch)+count(t->rch)+1;return t;}
  node* merge(node *l, node *r){
    if(!l || !r)return !l?r:l;
    if(l->pri > r->pri){
      l->rch = merge(l->rch,r);
      return update(l);
    }else{
      r->lch = merge(l,r->lch);
      return update(r);
    }
  }
  pair<node*,node*> split(node *t, ll k){
    if(!t) return make_pair<node*,node*>(NULL,NULL);
    if(k <= count(t->lch)){
      pair<node*,node*> s = split(t->lch,k);
      t->lch = s.second;
      return make_pair(s.first,update(t));
    }else{
      pair<node*,node*> s = split(t->rch,k-count(t->lch)-1);
      t->rch = s.first;
      return make_pair(update(t),s.second);
    }
  }
  ll __find(node *p,ll v){
    if(!p)return 0;
    if(p->val==v)return count(p->lch);
    return (lsss(v,p->val))?__find(p->lch,v):(count(p->lch)+1+__find(p->rch,v));
  }
  ll __lsss(node *p,ll v){
    if(!p)return 0;
    return (!lsss(p->val,v))?__lsss(p->lch,v):(count(p->lch)+1+__lsss(p->rch,v));
  }
  ll __lsss_eq(node *p,ll v){
    if(!p)return 0;
    return (lsss(v,p->val))?__lsss_eq(p->lch,v):(count(p->lch)+1+__lsss_eq(p->rch,v));
  }
  ll __get_at(node *p,ll k,ll acc){
    if(!p)return -1;
    ll lc=count(p->lch);
    if(acc+lc==k)return p->val;
    if(acc+lc>k)return __get_at(p->lch,k,acc);
    if(acc+lc<k)return __get_at(p->rch,k,acc+lc+1);
  }
public:
  void merge(Treap that){
    root = merge(root, that.root);
  }
  Treap split(ll k){
    Treap that;
    pair<node*,node*> p = split(root,k);
    root = p.first;
    that.root = p.second;
    return that;
  }
  void insert_at(ll v,ll k){
    pair<node*,node*> p = split(root,k);
    node* nn = new node(v);
    root = merge(p.first, nn);
    root = merge(root, p.second);
  }
  void erase_at(ll k){
    pair<node*,node*> p,q;
    q = split(root,k+1);
    p = split(q.first,k);
    root = merge(p.first, q.second);
  }
  void insert_by(ll v){
    insert_at(v,__lsss(root,v));
  }
  void erase_by(ll v){
    erase_at(__find(root,v));
  }
  ll count_lsss(ll v){
    return __lsss(root,v);
  }
  ll count_lsss_equal(ll v){
    return __lsss_eq(root,v);
  }
  ll get_at(ll k){
    return __get_at(root,k,0);
  }
  ll size(){
    return count(root);
  }
};

int n;
int a[252];
int b[252];

int calc(int a,int b){
  return 50*a+(int)((500*a)/(8+2*b));
}

unordered_map<string,int> id;
pii score[125252];

bool lsss(int x,int y){
  if(score[x].first != score[y].first) return score[x].first > score[y].first;
  return score[x].second > score[y].second;
}

int main(){
  scanf("%d",&n);
  REP(i,n)scanf("%d",a+i);
  REP(i,n)b[i] = 1;
  Treap *tr = new Treap();
  int t;
  scanf("%d",&t);
  int m=0;
  while(t--){
    string nm;
    string p;
    cin>>nm>>p;
    if(p=="?"){
      // query
      int x = id[nm];
      printf("%d\n",(int)tr->count_lsss(x)+1);
    }else{
      int po = p[0]-'A';
      int x;
      if(!id.count(nm)){
        x = m;
        id[nm] = m++;
      }else{
        x = id[nm];
        tr->erase_by(x);
      }
      x = id[nm];
      score[x].first += calc(a[po],b[po]);
      score[x].second = t;
      tr->insert_by(x);
      b[po]++;
    }
  }
  return 0;
}
0