結果

問題 No.2421 entersys?
ユーザー through
提出日時 2023-08-12 15:04:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 794 ms / 3,000 ms
コード長 3,521 bytes
コンパイル時間 4,592 ms
コンパイル使用メモリ 284,516 KB
最終ジャッジ日時 2025-02-16 05:40:31
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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