結果

問題 No.449 ゆきこーだーの雨と雪 (4)
ユーザー PachicobuePachicobue
提出日時 2018-02-23 19:06:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 293 ms / 5,000 ms
コード長 7,669 bytes
コンパイル時間 4,114 ms
コンパイル使用メモリ 233,036 KB
実行使用メモリ 17,728 KB
最終ジャッジ日時 2023-10-23 16:08:25
合計ジャッジ時間 11,835 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,784 KB
testcase_01 AC 3 ms
6,788 KB
testcase_02 AC 3 ms
6,784 KB
testcase_03 AC 21 ms
6,808 KB
testcase_04 AC 5 ms
6,812 KB
testcase_05 AC 5 ms
6,812 KB
testcase_06 AC 4 ms
6,808 KB
testcase_07 AC 5 ms
6,808 KB
testcase_08 AC 4 ms
6,808 KB
testcase_09 AC 4 ms
6,808 KB
testcase_10 AC 4 ms
6,808 KB
testcase_11 AC 4 ms
6,812 KB
testcase_12 AC 170 ms
7,036 KB
testcase_13 AC 253 ms
9,780 KB
testcase_14 AC 188 ms
9,768 KB
testcase_15 AC 293 ms
9,772 KB
testcase_16 AC 215 ms
9,764 KB
testcase_17 AC 217 ms
9,776 KB
testcase_18 AC 170 ms
7,036 KB
testcase_19 AC 213 ms
9,772 KB
testcase_20 AC 180 ms
9,760 KB
testcase_21 AC 249 ms
9,768 KB
testcase_22 AC 259 ms
9,784 KB
testcase_23 AC 171 ms
7,036 KB
testcase_24 AC 216 ms
9,768 KB
testcase_25 AC 136 ms
7,036 KB
testcase_26 AC 100 ms
7,036 KB
testcase_27 AC 253 ms
9,772 KB
testcase_28 AC 267 ms
9,776 KB
testcase_29 AC 191 ms
9,756 KB
testcase_30 AC 289 ms
9,772 KB
testcase_31 AC 257 ms
9,784 KB
testcase_32 AC 189 ms
9,764 KB
testcase_33 AC 219 ms
9,776 KB
testcase_34 AC 136 ms
7,036 KB
testcase_35 AC 286 ms
9,776 KB
testcase_36 AC 136 ms
7,036 KB
testcase_37 AC 204 ms
17,728 KB
testcase_38 AC 139 ms
12,264 KB
testcase_39 AC 107 ms
12,264 KB
testcase_40 AC 110 ms
12,264 KB
testcase_41 AC 258 ms
12,260 KB
testcase_42 AC 228 ms
12,260 KB
testcase_43 AC 63 ms
7,004 KB
testcase_44 AC 78 ms
7,172 KB
testcase_45 AC 138 ms
17,728 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using 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;
}
0