結果

問題 No.2421 entersys?
ユーザー dyktr_06dyktr_06
提出日時 2023-07-20 14:58:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 515 ms / 3,000 ms
コード長 5,068 bytes
コンパイル時間 2,667 ms
コンパイル使用メモリ 241,180 KB
実行使用メモリ 40,908 KB
最終ジャッジ日時 2024-09-20 11:11:24
合計ジャッジ時間 13,427 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 4 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 4 ms
5,376 KB
testcase_09 AC 5 ms
5,376 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 478 ms
29,024 KB
testcase_12 AC 459 ms
29,028 KB
testcase_13 AC 456 ms
29,136 KB
testcase_14 AC 467 ms
28,992 KB
testcase_15 AC 460 ms
29,128 KB
testcase_16 AC 498 ms
35,104 KB
testcase_17 AC 498 ms
35,084 KB
testcase_18 AC 506 ms
35,048 KB
testcase_19 AC 502 ms
35,072 KB
testcase_20 AC 496 ms
35,084 KB
testcase_21 AC 498 ms
34,360 KB
testcase_22 AC 430 ms
28,572 KB
testcase_23 AC 510 ms
40,692 KB
testcase_24 AC 507 ms
40,664 KB
testcase_25 AC 515 ms
40,908 KB
testcase_26 AC 342 ms
20,852 KB
testcase_27 AC 343 ms
21,088 KB
testcase_28 AC 345 ms
20,852 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