結果

問題 No.2421 entersys?
ユーザー dyktr_06dyktr_06
提出日時 2023-07-20 14:58:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 584 ms / 3,000 ms
コード長 5,068 bytes
コンパイル時間 3,223 ms
コンパイル使用メモリ 241,184 KB
実行使用メモリ 40,940 KB
最終ジャッジ日時 2023-10-20 15:39:34
合計ジャッジ時間 14,023 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 3 ms
4,348 KB
testcase_02 AC 4 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 3 ms
4,348 KB
testcase_05 AC 4 ms
4,348 KB
testcase_06 AC 4 ms
4,348 KB
testcase_07 AC 4 ms
4,348 KB
testcase_08 AC 4 ms
4,348 KB
testcase_09 AC 5 ms
4,348 KB
testcase_10 AC 4 ms
4,348 KB
testcase_11 AC 472 ms
29,216 KB
testcase_12 AC 480 ms
29,224 KB
testcase_13 AC 485 ms
29,200 KB
testcase_14 AC 484 ms
29,188 KB
testcase_15 AC 473 ms
29,196 KB
testcase_16 AC 523 ms
35,056 KB
testcase_17 AC 519 ms
35,036 KB
testcase_18 AC 521 ms
35,000 KB
testcase_19 AC 519 ms
35,024 KB
testcase_20 AC 537 ms
35,032 KB
testcase_21 AC 532 ms
34,588 KB
testcase_22 AC 435 ms
28,636 KB
testcase_23 AC 553 ms
40,940 KB
testcase_24 AC 546 ms
40,916 KB
testcase_25 AC 584 ms
40,900 KB
testcase_26 AC 356 ms
21,064 KB
testcase_27 AC 357 ms
21,328 KB
testcase_28 AC 366 ms
21,068 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

template <typename T>
struct BinaryIndexedTree{
    int N;
    vector<T> BIT;
    BinaryIndexedTree(const int &N): N(N), BIT(N + 1, 0){
    }

    T get(int i){
        return sum(i + 1) - sum(i);
    }

    void add(int i, T x){
        i++;
        while(i <= N){
            BIT[i] += x;
            i += i & -i;
        }
    }

    T sum(int i) const {
        T ans = 0;
        while(i > 0){
            ans += BIT[i];
            i -= i & -i;
        }
        return ans;
    }

    T sum(int L, int R) const {
        return sum(R) - sum(L);
    }

    int lower_bound(T x) const {
        if(x <= 0){
            return 0;
        }else{
            int v = 0, r = 1;
            while(r < N) r = r << 1;
            for(int len = r; len > 0; len = len >> 1){
                if(v + len < N && BIT[v + len] < x){
                    x -= BIT[v + len];
                    v += len;
                }
            }
            return v;
        }
    }

    int upper_bound(T x) const {
        if(x < 0){
            return 0;
        }else{
            int v = 0, r = 1;
            while(r <= N) r = r << 1;
            for(int len = r; len > 0; len = len >> 1){
                if(v + len <= N && BIT[v + len] <= x){
                    x -= BIT[v + len];
                    v += len;
                }
            }
            return v;
        }
    }

    T operator [](int i) const {
        return sum(i, i + 1);
    }
};

template <typename T>
struct compress{
    vector<T> sorted, compressed;

    compress(const vector<T>& vec){
        int n = vec.size();
        compressed.resize(n);
        for(T x : vec){
            sorted.emplace_back(x);
        }
        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
        for(int i = 0; i < n; ++i){
            compressed[i] = lower_bound(sorted.begin(), sorted.end(), vec[i]) - sorted.begin();
        }
    }

    int get(const T& x) const{
        return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
    }

    T inv(const T& x) const{
        return sorted[x];
    }

    size_t size() const{
        return sorted.size();
    }

    vector<T> getCompressed() const{
        return compressed;
    }
};

int conv(string s){
    int res = 0, n = s.size();
    int p = 1;
    for(int i = 0; i < n; i++){
        res += (s[i] - 'A' + 1) * p;
        p *= 27;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    map<int, vector<int>> time;
    vector<string> X(N);
    vector<int> XC(N), L(N), R(N);
    vector<int> XCC = {0};
    for(int i = 0; i < N; i++){
        cin >> X[i] >> L[i] >> R[i];
        XC[i] = conv(X[i]);
        time[0].push_back(L[i]);
        time[0].push_back(R[i] + 1);
        time[XC[i]].push_back(L[i]);
        time[XC[i]].push_back(R[i] + 1);
        XCC.push_back(XC[i]);
    }

    int Q; cin >> Q;
    vector<tuple<int, int, int, int>> query(Q);
    for(int i = 0; i < Q; i++){
        int type; cin >> type;
        if(type == 1){
            string x; int t; cin >> x >> t;
            int xc = conv(x);
            query[i] = {type, xc, t, 0};
            time[xc].push_back(t);
            XCC.push_back(xc);
        }else if(type == 2){
            int t; cin >> t;
            query[i] = {type, t, 0, 0};
            time[0].push_back(t);
        }else{
            string x; int l, r; cin >> x >> l >> r;
            int xc = conv(x);
            query[i] = {type, xc, l, r};
            time[0].push_back(l);
            time[0].push_back(r + 1);
            time[xc].push_back(l);
            time[xc].push_back(r + 1);
            XCC.push_back(xc);
        }
    }

    compress<int> XCCcomp(XCC);
    int M = XCCcomp.size();
    vector<compress<int>> comp(M, compress<int>(vector<int>(0)));
    vector<BinaryIndexedTree<int>> BIT(M, BinaryIndexedTree<int>(0));
    
    for(auto [k, x] : time){
        int idx = XCCcomp.get(k);
        comp[idx] = compress<int>(x);
        BIT[idx] = BinaryIndexedTree<int>(comp[idx].size());
    }

    for(int i = 0; i < N; i++){
        BIT[0].add(comp[0].get(L[i]), 1);
        BIT[0].add(comp[0].get(R[i] + 1), -1);

        int idx = XCCcomp.get(XC[i]);
        BIT[idx].add(comp[idx].get(L[i]), 1);
        BIT[idx].add(comp[idx].get(R[i] + 1), -1);
    }

    for(int i = 0; i < Q; i++){
        auto [type, a, b, c] = query[i];
        if(type == 1){
            int idx = XCCcomp.get(a);
            if(BIT[idx].sum(0, comp[idx].get(b) + 1) == 1){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }else if(type == 2){
            cout << BIT[0].sum(0, comp[0].get(a) + 1) << endl;
        }else{
            int idx = XCCcomp.get(a);
            BIT[0].add(comp[0].get(b), 1);
            BIT[0].add(comp[0].get(c + 1), -1);
            BIT[idx].add(comp[idx].get(b), 1);
            BIT[idx].add(comp[idx].get(c + 1), -1);
        }
    }
}
0