結果

問題 No.449 ゆきこーだーの雨と雪 (4)
ユーザー tnakao0123tnakao0123
提出日時 2016-11-23 21:48:44
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 295 ms / 5,000 ms
コード長 4,581 bytes
コンパイル時間 926 ms
コンパイル使用メモリ 97,732 KB
実行使用メモリ 37,736 KB
最終ジャッジ日時 2024-09-22 10:28:13
合計ジャッジ時間 9,826 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
9,676 KB
testcase_01 AC 4 ms
9,804 KB
testcase_02 AC 3 ms
9,804 KB
testcase_03 AC 4 ms
9,936 KB
testcase_04 AC 5 ms
11,984 KB
testcase_05 AC 4 ms
9,940 KB
testcase_06 AC 4 ms
9,804 KB
testcase_07 AC 5 ms
9,928 KB
testcase_08 AC 4 ms
9,928 KB
testcase_09 AC 4 ms
9,676 KB
testcase_10 AC 4 ms
9,800 KB
testcase_11 AC 4 ms
9,932 KB
testcase_12 AC 169 ms
12,672 KB
testcase_13 AC 212 ms
19,104 KB
testcase_14 AC 240 ms
19,264 KB
testcase_15 AC 199 ms
18,980 KB
testcase_16 AC 234 ms
18,832 KB
testcase_17 AC 237 ms
18,868 KB
testcase_18 AC 171 ms
12,548 KB
testcase_19 AC 239 ms
18,644 KB
testcase_20 AC 239 ms
19,296 KB
testcase_21 AC 211 ms
19,588 KB
testcase_22 AC 218 ms
20,056 KB
testcase_23 AC 168 ms
14,040 KB
testcase_24 AC 227 ms
19,576 KB
testcase_25 AC 185 ms
11,728 KB
testcase_26 AC 208 ms
10,960 KB
testcase_27 AC 295 ms
19,616 KB
testcase_28 AC 210 ms
20,540 KB
testcase_29 AC 232 ms
18,816 KB
testcase_30 AC 198 ms
19,152 KB
testcase_31 AC 233 ms
18,956 KB
testcase_32 AC 233 ms
18,884 KB
testcase_33 AC 222 ms
20,128 KB
testcase_34 AC 187 ms
13,720 KB
testcase_35 AC 204 ms
19,896 KB
testcase_36 AC 185 ms
12,808 KB
testcase_37 AC 207 ms
37,544 KB
testcase_38 AC 239 ms
24,836 KB
testcase_39 AC 207 ms
25,140 KB
testcase_40 AC 209 ms
25,208 KB
testcase_41 AC 183 ms
24,948 KB
testcase_42 AC 179 ms
24,900 KB
testcase_43 AC 160 ms
14,160 KB
testcase_44 AC 100 ms
12,904 KB
testcase_45 AC 151 ms
37,736 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 449.cc: No.447 ゆきこーだーの雨と雪 (4) - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 26;
const int MAX_T = 100000;
const int INF = 1 << 30;

/* typedef */

typedef map<string,int> msi;

struct Stat {
  int id, sum, t;
  Stat() {}
  Stat(int _id, int _sum, int _t): id(_id), sum(_sum), t(_t) {}
  bool operator<(const Stat &s) const {
    return sum > s.sum || (sum == s.sum && t < s.t);
  }
  bool operator==(const Stat &s) const {
    return sum == s.sum && t == s.t;
  }
};

const Stat STINF(-1, -1, INF);

template <typename T, const int BUFSIZE>
struct Treap {
  struct Node {
    T key;
    int fix, size;
    Node *left, *right;

    void print(int k) {
      printf("%d: key=%lld, fix=%d, size=%d\n",
	     k, key, fix, size);
    }
    void print() { print(0); }
  };
  typedef Node *node;

  node root, nullnode, buf;
  Node buf0[BUFSIZE], buf1;

  const T TINF;
  
  Treap(T tinf): TINF(tinf) {
    nullnode = &buf1;
    nullnode->left = nullnode->right = nullnode;
    nullnode->fix = nullnode->size = 0;
    clear();
    srand(time(NULL));
  }

  void clear() { buf = buf0; root = nullnode; }
  
  int size() { return root->size; }

  void update(node& t) {
    t->size = 1 + t->left->size + t->right->size;
  }

  node gen_node(T x) {
    node t = buf++;
    t->left = t->right = nullnode;
    t->key = x;
    t->fix = rand();
    t->size = 1;
    return t;
  }
  
  void rot_l(node& k1) {
    node k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    update(k1);
    update(k2);
    k1 = k2;
  }

  void rot_r(node& k1) {
    node k2 = k1->left;
    k1->left = k2->right;
    k2->right = k1;
    update(k1);
    update(k2);
    k1 = k2;
  }

  void insert(node& t, T x) {
    if (t == nullnode)
      t = gen_node(x);
    else {
      if (t->key == x) return;
      if (x < t->key) {
	insert(t->left, x);
	update(t);
	if (t->left->fix > t->fix) rot_r(t);
      }
      else {
	insert(t->right, x);
	update(t);
	if (t->right->fix > t->fix) rot_l(t);
      }
    }
  }
  void insert(T x) { insert(root, x); }

  void remove_node(node& t) {
    if (t == nullnode) return;
    if (t->left == nullnode || t->right == nullnode) {
      if (t->left == nullnode)
	t = t->right;
      else
	t = t->left;
    }
    else {
      if (t->left->fix < t->right->fix) {
	rot_l(t);
	remove_node(t->left);
	update(t);
      }
      else {
	rot_r(t);
	remove_node(t->right);
	update(t);
      }
    }
  }

  void remove(node& t, T x) {
    if (t != nullnode) {
      if (t->key == x)
	remove_node(t);
      else if (x < t->key) {
	remove(t->left, x);
	update(t);
      }
      else {
	remove(t->right, x);
	update(t);
      }
    }
  }
  void remove(T x) { remove(root, x); }
  
  int lower_bound(T x) {
    node t = root;
    int k = 0;

    while (t != nullnode) {
      if (t->key < x) {
	k += t->left->size + 1;
	t = t->right;
      }
      else {
	t = t->left;
      }
    }
    return k;
  }
  
  void print(node t, int k, int indent) {
    if (t == nullnode) return;
    if (t != NULL) {
      for (int i = 0; i < indent; i++) cout << "  ";
      t->print(k + t->left->size);
      print(t->left, k, indent + 1);
      print(t->right, k + t->left->size + 1, indent + 1);
    }
  }
  void print() { print(root, 0, 0); }
};

/* global variables */

int ls[MAX_N], acs[MAX_N], scs[MAX_T][MAX_N];
Stat ss[MAX_T];
string nms[MAX_T];
msi nmmap;
Treap<Stat,MAX_T> trp(STINF);

/* subroutines */

/* main */

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> ls[i];

  int t, m = 0;
  cin >> t;


  for (int i = 0; i < t; i++) {
    string nmi, pi;
    cin >> nmi >> pi;

    msi::iterator mit = nmmap.find(nmi);
    int id;
    bool newst = false;
    if (mit == nmmap.end()) {
      id = nmmap[nmi] = m++;
      nms[id] = nmi;
      ss[id] = Stat(id, 0, 0);
      newst = true;
    }
    else id = mit->second;
    Stat &ssi = ss[id];

    if (pi[0] == '?') {
      int k = trp.lower_bound(ssi);
      printf("%d\n", k + 1);
    }
    else {
      if (! newst) trp.remove(ssi);

      int li = pi[0] - 'A';
      scs[id][li] = 50 * ls[li] + (50 * ls[li]) * 5 / (4 + ++acs[li]);
      ssi.sum += scs[id][li];
      ssi.t = i;

      trp.insert(ssi);
    }
  }
  return 0;
}
0