結果

問題 No.2421 entersys?
ユーザー 0214sh70214sh7
提出日時 2023-08-12 15:29:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,812 bytes
コンパイル時間 3,533 ms
コンパイル使用メモリ 245,372 KB
実行使用メモリ 31,004 KB
最終ジャッジ日時 2024-11-20 02:48:09
合計ジャッジ時間 23,777 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PP;
//#define MOD 1000000007
#define MOD 998244353
#define INF 2305843009213693951
//#define INF 810114514
#define PI 3.141592653589
#define setdouble setprecision
#define REP(i,n) for(ll i=0;i<(n);++i)
#define OREP(i,n) for(ll i=1;i<=(n);++i)
#define RREP(i,n) for(ll i=(n)-1;i>=0;--i)
#define ALL(v) (v).begin(), (v).end()
#define GOODBYE do { cout << "-1" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug true
#define debug2 false

template<typename T>
class segmenttree{
    // Copyright (c) 2023 0214sh7
    // https://github.com/0214sh7/library/
    private:
    int n;
    
    std::vector<T> dat;
    std::function<T(T,T)> calc;
    T identity;
    public:
    
    void init(int N,std::function<T(T,T)> func,T Identity){
        n=1;
        while(n<N)n*=2;
        dat.resize(2*n-1);
        for(int i=0;i<2*n-1;++i){
            dat[i]=Identity;
        }
        calc = func;
        identity = Identity;
    }
    
    segmenttree(int N,std::function<T(T,T)> func,T Identity){
        init(N,func,Identity);
    }
    
    void update(int k,T a){
        k+=n-1;
        dat[k]=a;
        while(k>0){
            k=(k-1)/2;
            dat[k]=calc(dat[2*k+1],dat[2*k+2]);
        }
    }
    
    T query(int a,int b){
        a+=n-1;
        b+=n-1;
        T L= identity,R = identity;
        while(a < b){
            if(a % 2 == 0){
                L = calc(L,dat[a]);
                a++;
            }
            a = (a-1)/2;
            if(b % 2 == 0){
                R = calc(dat[b-1],R);
                b--;
            }
            b = (b-1)/2;
        }
        R = calc(L,R);
        return R;
    }
    
};

class compress{
    // Copyright (c) 2023 0214sh7
    // https://github.com/0214sh7/library/
    private:
    std::vector<int> E;
    
    public:
    void init(std::vector<long long> A){
        E.clear();
        sort(A.begin(),A.end());
        for(int i=0;i<A.size();i++){
            if(i==0 || A[i]!=A[i-1]){
                E.push_back(A[i]);
            }
        }
    }
    
    compress(std::vector<long long> A){
        init(A);
    }
    
    int size(){
        return (int)E.size();
    }
    
    int value(int x){
        if(0<=x && x<(int)E.size()){
            return E[x];
        }else{
            return 0;
        }
    }
    
    int index(int X){
        return (upper_bound(E.begin(),E.end(),X))-E.begin()-1;
    }
    
};

int main(void){
    //cin.tie(nullptr);
    //ios::sync_with_stdio(false);
    
    ll N;
    cin >> N;
    vector<string> X(N);
    vector<ll> L(N),R(N);
    REP(i,N){
        cin >> X[i] >> L[i] >> R[i];
    }

    map<string,ll> index;
    REP(i,N){
        if(index[X[i]]==0){
            index[X[i]] = index.size();
        }
    }

    /*for(auto it = index.begin();it!=index.end();it++){
        cout << (it->first) MM (it->second) << endl;
    }*/

    ll Q;
    cin >> Q;
    vector<array<ll,4>> que(Q);
    REP(i,Q){
        ll c;
        cin >> c;
        if(c==1){
            string x;
            ll t;
            cin >> x >> t;
            que[i] = {c,index[x]-1,t,-1};
        }else if(c==2){
            ll t;
            cin >> t;
            que[i] = {c,t,-1,-1};
        }else{
            string x;
            ll l,r;
            cin >> x >> l >> r;
            if(index[x]==0){
                index[x] = index.size();
            }
            que[i] = {c,index[x]-1,l,r};
        }
    }

    //全体のクエリ情報を座圧する
    vector<ll> Z;
    REP(i,N){
        Z.push_back(L[i]);
    }
    REP(i,N){
        Z.push_back(R[i]);
    }
    REP(i,Q){
        if(que[i][0]==1){
            Z.push_back(que[i][2]);
        }else if(que[i][0]==2){
            Z.push_back(que[i][1]);
        }else{
            Z.push_back(que[i][2]);
            Z.push_back(que[i][3]);
        }
    }
    compress Za(Z);
    REP(i,N){
        L[i] = Za.index(L[i]);
        R[i] = Za.index(R[i]);
    }
    REP(i,Q){
        if(que[i][0]==1){
            que[i][2] = Za.index(que[i][2]);
        }else if(que[i][0]==2){
            que[i][1] = Za.index(que[i][1]);
        }else{
            que[i][2] = Za.index(que[i][2]);
            que[i][3] = Za.index(que[i][3]);
        }
    }

    //個人で座圧する
    vector<ll> Li = L, Ri=R;
    vector<array<ll,4>> quei = que;
    vector<vector<ll>> I(index.size());
    REP(i,N){
        I[index[X[i]]].push_back(L[i]);
        I[index[X[i]]].push_back(R[i]);
    }
    REP(i,Q){
        if(que[i][0]==1){
            I[que[i][1]].push_back(que[i][2]);
        }else if(que[i][0]==3){
            I[que[i][1]].push_back(que[i][2]);
            I[que[i][1]].push_back(que[i][3]);
        }
    }
    vector<compress> Zi;
    REP(i,index.size()){
        Zi.push_back(compress(I[i]));
    }
    REP(i,N){
        Li[i] = Zi[index[X[i]]].index(L[i]);
        Ri[i] = Zi[index[X[i]]].index(R[i]);
    }
    REP(i,Q){
        if(que[i][0]==1){
            quei[i][2] = Zi[quei[i][1]].index(que[i][2]);
        }else if(que[i][0]==3){
            quei[i][2] = Zi[quei[i][1]].index(que[i][2]);
            quei[i][3] = Zi[quei[i][1]].index(que[i][3]);
        }
    }

    //全体と個人でそれぞれセグ木を用意
    std::function<long long(long long,long long)> func = [](long long a,long long b){
        return a+b;
    };
    segmenttree<long long> SEG(Za.size()+1,func,0);
    vector<segmenttree<long long>> SEGi;
    REP(i,index.size()){
        SEGi.push_back(segmenttree<long long>(Zi[i].size()+1,func,0));
    }

    vector<ll> D(Za.size()+1,0);
    vector<vector<ll>> Di(index.size());
    REP(i,index.size()){Di[i].assign(Zi[i].size()+1,0);}

    REP(i,N){
        ll x = index[X[i]], l = L[i], r = R[i];
        D[l]++;
        SEG.update(l,D[l]);
        D[r+1]--;
        SEG.update(r+1,D[r+1]);

        Di[x][Li[i]]++;
        SEGi[x].update(Li[i],Di[x][Li[i]]);
        Di[x][Ri[i]+1]++;
        SEGi[x].update(Ri[i],Di[x][Ri[i]+1]);

    }


    REP(i,Q){
        if(que[i][0]==1){
            ll Ans = SEGi[que[i][1]].query(0,quei[i][2]+1);
            //cout << Ans << "  ";
            if(Ans%2==1){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }

        }else if(que[i][0]==2){
            ll Ans = SEG.query(0,que[i][1]+1);
            cout << Ans << endl;
        }else{

            ll x = que[i][1], l = que[i][2], r = que[i][3];
            D[l]++;
            SEG.update(l,D[l]);
            D[r+1]--;
            SEG.update(r+1,D[r+1]);

            Di[x][Li[i]]++;
            SEGi[x].update(Li[i],Di[x][Li[i]]);
            Di[x][Ri[i]+1]++;
            SEGi[x].update(Ri[i],Di[x][Ri[i]+1]);
        }
    }

    return 0;
}
0