結果

問題 No.2421 entersys?
ユーザー throughthrough
提出日時 2023-08-12 15:04:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,013 ms / 3,000 ms
コード長 3,521 bytes
コンパイル時間 5,810 ms
コンパイル使用メモリ 297,600 KB
実行使用メモリ 63,284 KB
最終ジャッジ日時 2024-11-19 23:20:21
合計ジャッジ時間 21,886 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 5 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 4 ms
5,248 KB
testcase_06 AC 4 ms
5,248 KB
testcase_07 AC 5 ms
5,248 KB
testcase_08 AC 5 ms
5,248 KB
testcase_09 AC 6 ms
5,248 KB
testcase_10 AC 4 ms
5,248 KB
testcase_11 AC 772 ms
46,816 KB
testcase_12 AC 761 ms
46,840 KB
testcase_13 AC 792 ms
46,816 KB
testcase_14 AC 756 ms
46,812 KB
testcase_15 AC 753 ms
46,828 KB
testcase_16 AC 811 ms
53,192 KB
testcase_17 AC 781 ms
53,028 KB
testcase_18 AC 800 ms
53,016 KB
testcase_19 AC 798 ms
52,976 KB
testcase_20 AC 798 ms
53,016 KB
testcase_21 AC 738 ms
48,460 KB
testcase_22 AC 566 ms
48,524 KB
testcase_23 AC 1,013 ms
63,212 KB
testcase_24 AC 997 ms
63,284 KB
testcase_25 AC 1,004 ms
63,144 KB
testcase_26 AC 483 ms
37,392 KB
testcase_27 AC 492 ms
37,388 KB
testcase_28 AC 495 ms
37,516 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using T = tuple<ll, string, ll, ll, ll>;
#include <atcoder/all>
using namespace atcoder;
// using mint = modint1000000007;
#define rep(i, n) for(ll i = 0; i < n; i++)

// S が data, F が lazy
using S = ll;
using F = ll;
// operator(作用素)
S op(S a,S b){
    return a+b;
}
// 遅延データ反映
S mapping(F f,S x){
    return f+x;
}
// 遅延データ作用
F composition(F f,F g){
    return f+g;
}
S e(){ return 0; } // 単位元 (op(e, a) = op(a, e) = a)
F id(){ return 0; } // mapping(id, a) = a

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    
    ll n; cin >> n;
    vector<ll> comp;
    map<string,set<ll>> nyu, tai;
    vector<P> kukan;
    rep(i,n) {
        string x; ll l,r; cin >> x >> l >> r;
        nyu[x].insert(l);
        tai[x].insert(r);
        comp.push_back(l);
        comp.push_back(r);
        kukan.push_back(P(l,r));
    }

    ll q; cin >> q;
    vector<T> query(q);

    rep(i,q) {
        ll qq; cin >> qq;
        if( qq == 1 ) {
            string x; ll t; cin >> x >> t;
            query[i] = T(qq,x,-1,-1,t);
            comp.push_back(t);
        }
        else if( qq == 2 ) {
            ll t; cin >> t;
            query[i] = T(qq,"",-1,-1,t);
            comp.push_back(t);
        }
        else {
            string x; ll l,r; cin >> x >> l >> r;
            query[i] = T(qq,x,l,r,-1);
            comp.push_back(l);
            comp.push_back(r);
        }
    }
    sort(comp.begin(),comp.end());
    comp.erase( unique(comp.begin(),comp.end()), comp.end() );

    lazy_segtree<S,op,e,F,mapping,composition,id> lsg(comp.size());
    rep(i,kukan.size()) {
        auto &&[l,r] = kukan[i];
        ll i1 = lower_bound(comp.begin(), comp.end(), l) - comp.begin();
        ll i2 = lower_bound(comp.begin(), comp.end(), r) - comp.begin();
        lsg.apply(i1,i2+1,1);
    }

    rep(i,q) {
        auto &&[qq,x,l,r,t] = query[i];
        if( qq == 1 ) {
            auto itr1 = nyu[x].upper_bound(t);
            if( itr1 == nyu[x].begin() ) {
                cout << "No" << endl;
                continue;
            }
            itr1--;
            auto itr2 = tai[x].upper_bound(*itr1);
            if( itr2 == tai[x].end() || *itr2 < t ) cout << "No" << endl;
            else cout << "Yes" << endl;
        }
        else if( qq == 2 ) {
            ll i = lower_bound(comp.begin(), comp.end(), t) - comp.begin();
            // cout << i << " " << comp.size() << endl << flush;
            cout << lsg.get(i) << endl;
        }
        else {
            // cout << "Yeah!" << endl << flush;
            ll i1 = lower_bound(comp.begin(), comp.end(), l) - comp.begin();
            ll i2 = lower_bound(comp.begin(), comp.end(), r) - comp.begin();
            // cout << i1 << " " << i2 << endl << flush;
            lsg.apply(i1,i2+1,1);
            if( tai[x].count(l) && nyu[x].count(r) ) {
                tai[x].erase(tai[x].find(l));
                nyu[x].erase(nyu[x].find(r));
            }
            else if( tai[x].count(l) && !nyu[x].count(r) ) {
                tai[x].erase(tai[x].find(l));
                tai[x].insert(r);
            }
            else if( !tai[x].count(l) && nyu[x].count(r) ) {
                nyu[x].erase(tai[x].find(r));
                nyu[x].insert(l);
            }
            else {
                nyu[x].insert(l);
                tai[x].insert(r);
            }
        }
    }

    return 0;
}
0