結果
問題 | No.449 ゆきこーだーの雨と雪 (4) |
ユーザー |
|
提出日時 | 2018-02-23 19:06:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 315 ms / 5,000 ms |
コード長 | 7,669 bytes |
コンパイル時間 | 3,305 ms |
コンパイル使用メモリ | 222,508 KB |
最終ジャッジ日時 | 2025-01-05 08:27:37 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include <bits/stdc++.h>#define show(x) cerr << #x << " = " << x << endlusing namespace std;template <typename S, typename T>ostream& operator<<(ostream& os, const pair<S, T>& p){os << "(" << p.first << "," << p.second<< ")";return os;}struct OrderedSet {public:static constexpr int POOL_SIZE = 100000;private:struct Node {using T = pair<int, int>;using Ptr = Node*;using PtrPair = pair<Ptr, Ptr>;Node() : left{}, right{}, value{}, size{1} {}Node(const T& value) : left{}, right{}, value{value}, size{1} {}Ptr left, right;T value;int size;static void serialize(Ptr a, vector<T>& v){if (a == nullptr) {return;} else {serialize(a->left, v);v.push_back(a->value);serialize(a->right, v);}}static unsigned xor128(){static unsigned x = 123456789;static unsigned y = 362436069;static unsigned z = 521288629;static unsigned w = 88675123;const unsigned t = x ^ (x << 11);x = y;y = z;z = w;return w = (w ^ (w << 19)) ^ (t ^ (t >> 8));}static unsigned getRand(const int maximum){return xor128() % maximum;}static int getSize(const Ptr a){return (a == nullptr) ? 0 : a->size;}static Ptr update(Ptr a){a->size = getSize(a->left) + getSize(a->right) + 1;return a;}static Ptr merge(Ptr a, Ptr b){if (a == nullptr) {return b;} else if (b == nullptr) {return a;}const unsigned asize = getSize(a);const unsigned bsize = getSize(b);if (getRand(asize + bsize) < asize) {a->right = merge(a->right, b);return update(a);} else {b->left = merge(a, b->left);return update(b);}}static PtrPair split(Ptr a, const int k) // size = (k,n-k){if (a == nullptr) {return make_pair(Ptr{}, Ptr{});}if (k <= getSize(a->left)) {const PtrPair s = split(a->left, k);a->left = s.second;return make_pair(s.first, update(a));} else {const PtrPair s = split(a->right, k - getSize(a->left) - 1);a->right = s.first;return make_pair(update(a), s.second);}}static Ptr insert(Ptr a, const int k, Ptr b){const PtrPair s = split(a, k);return merge(merge(s.first, b), s.second);}static PtrPair erase(Ptr a, const int k){const PtrPair sr = split(a, k + 1);const PtrPair sl = split(sr.first, k);return make_pair(merge(sl.first, sr.second), sl.second);}};using Ptr = typename Node::Ptr;using PtrPair = typename Node::PtrPair;Ptr root;int head = 0;static Node pool[POOL_SIZE];Ptr alloc(const Node::T& x){assert(head < POOL_SIZE);pool[head].value = x;pool[head].size = 1;pool[head].left = nullptr;pool[head].right = nullptr;head++;return pool + head - 1;}void garbage_collect(){vector<T> v;Node::serialize(root, v);head = 0;root = nullptr;for (int i = 0; i < v.size(); i++) {root = Node::insert(root, i, alloc(v[i]));}}public:using T = typename Node::T;OrderedSet() : root{} {}int size() const{return Node::getSize(root);}void insert(const T& value){if (head == POOL_SIZE) {garbage_collect();}const int pos = lowerBound(value);root = Node::insert(root, pos, alloc(value));}int lowerBound(const T& x) const{int res = 0;Ptr v = root;while (v) {if (x < v->value) {v = v->left;} else if (x == v->value) {return res + Node::getSize(v->left);} else {res += Node::getSize(v->left) + 1;v = v->right;}}return res;}int upperBound(const T& x) const{int res = 0;Ptr v = root;while (v) {if (x <= v->value) {v = v->left;} else if (x == v->value) {return res + Node::getSize(v->left);} else {res += Node::getSize(v->left) + 1;v = v->right;}}return res;}void eraseAt(const int k){assert(0 <= k);assert(k < Node::getSize(root));Ptr p;tie(root, p) = Node::erase(root, k);if (p != nullptr) {p->left = Ptr{};p->right = Ptr{};}}void erase(const T& value){const int pos = lowerBound(value);eraseAt(pos);}bool eraseWithCheck(const T& value){const int pos = lowerBound(value);if (pos == size()) {return false;} else if (upperBound(value) == pos) {return false;} else {eraseAt(pos);return true;}}T get(int k) const{assert(0 <= k);assert(k < Node::getSize(root));Ptr v = root;while (v != nullptr) {const int s = Node::getSize(v->left);if (s > k) {v = v->left;} else if (s == k) {return v->value;} else {v = v->right;k -= s + 1;}}return v->value;}void set(const int k, const T& value){assert(0 <= k);assert(k < Node::getSize(root));const PtrPair sr = Node::split(root, k + 1);const PtrPair sl = Node::split(sr.first, k);const Ptr lr = sl.second;lr->value = value;root = Node::merge(Node::merge(sl.first, lr), sr.second);}};OrderedSet::Node OrderedSet::pool[OrderedSet::POOL_SIZE];ostream& operator<<(ostream& os, const OrderedSet& st){os << "[";for (int i = 0; i < st.size(); i++) {os << st.get(i) << ",";}os << "]" << endl;return os;}int main(){cin.tie(0);ios::sync_with_stdio(false);int N;cin >> N;using S = pair<int, int>;vector<int> level(N);for (int i = 0; i < N; i++) {cin >> level[i];}int T;cin >> T;map<string, S> score;vector<int> solved(N, 0);OrderedSet st;for (int t = 0; t < T; t++) {string name;cin >> name;char P;cin >> P;if (P == '?') {const S s = score[name];cout << 1 + st.lowerBound(s) << "\n";} else {const int p = P - 'A';if (score.find(name) == score.end()) {} else {st.erase(score[name]);}solved[p]++;score[name] = {score[name].first - 50 * level[p] - 250 * level[p] / (4 + solved[p]), t};st.insert(score[name]);}}return 0;}