#131359 (C++11) No.449 ゆきこーだーの雨と雪 (4)

提出ソース

結果

問題	No.449 ゆきこーだーの雨と雪 (4)
ユーザー	rickytheta
提出日時	2016-11-18 23:04:32
言語	C++11 (gcc 11.4.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	4 ms 6,944 KB
testcase_04	AC	3 ms 6,940 KB
testcase_05	AC	3 ms 6,940 KB
testcase_06	AC	3 ms 6,940 KB
testcase_07	AC	3 ms 6,944 KB
testcase_08	AC	3 ms 6,944 KB
testcase_09	AC	3 ms 6,940 KB
testcase_10	AC	3 ms 6,944 KB
testcase_11	AC	3 ms 6,940 KB
testcase_12	AC	203 ms 6,944 KB
testcase_13	AC	235 ms 9,984 KB
testcase_14	AC	230 ms 8,704 KB
testcase_15	AC	227 ms 10,496 KB
testcase_16	AC	216 ms 9,448 KB
testcase_17	AC	220 ms 9,572 KB
testcase_18	AC	200 ms 6,940 KB
testcase_19	AC	223 ms 8,704 KB
testcase_20	AC	213 ms 8,832 KB
testcase_21	AC	221 ms 9,856 KB
testcase_22	AC	224 ms 10,004 KB
testcase_23	AC	201 ms 6,940 KB
testcase_24	AC	224 ms 9,320 KB
testcase_25	AC	205 ms 6,944 KB
testcase_26	AC	210 ms 6,944 KB
testcase_27	AC	220 ms 9,984 KB
testcase_28	AC	221 ms 9,984 KB
testcase_29	AC	220 ms 8,704 KB
testcase_30	AC	224 ms 10,492 KB
testcase_31	AC	227 ms 9,872 KB
testcase_32	AC	214 ms 8,704 KB
testcase_33	AC	214 ms 9,328 KB
testcase_34	AC	207 ms 6,940 KB
testcase_35	AC	224 ms 10,496 KB
testcase_36	AC	208 ms 6,940 KB
testcase_37	AC	142 ms 19,592 KB
testcase_38	AC	187 ms 11,480 KB
testcase_39	AC	172 ms 11,468 KB
testcase_40	AC	174 ms 11,472 KB
testcase_41	AC	148 ms 13,728 KB
testcase_42	AC	139 ms 13,776 KB
testcase_43	AC	162 ms 6,940 KB
testcase_44	AC	106 ms 8,064 KB
testcase_45	AC	135 ms 19,716 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

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);
      |   ~~~~~^~~~~~~~~

ソースコード

raw source code

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

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード