#903282 (C++17) No.2421 entersys?

提出ソース

結果

問題	No.2421 entersys?
ユーザー	0214sh7
提出日時	2023-08-12 16:13:39
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	7,435 bytes
コンパイル時間	3,503 ms
コンパイル使用メモリ	246,088 KB
実行使用メモリ	79,840 KB
最終ジャッジ日時	2024-11-20 05:16:21
合計ジャッジ時間	26,862 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	RE	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	WA	-
testcase_07	RE	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	WA	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	689 ms 57,612 KB
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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();
        }
    }

    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],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],l,r};
        }
    }

    

    for(auto it = index.begin();it!=index.end();it++){
        it->second -= 1;
    }

    //全体のクエリ情報を座圧する
    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(Za.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,N){
        cout << index[X[i]] MM L[i] MM R[i] << endl;
    }cout << endl;*/
    /*REP(i,N){
        cout << index[X[i]] MM Li[i] MM Ri[i] << endl;
    }cout << endl;*/

    /*REP(i,Za.size()){
        cout << SEG.query(0,i+1) << " ";
    }cout << endl;
    REP(j,index.size()){
        REP(i,Zi[j].size()){
            cout << SEGi[j].query(i,i+1) << " ";
        }cout << endl;
    }*/

    /*REP(i,Q){
        REP(j,4){
            cout << que[i][j] << " ";
        }
        cout << endl;
    }

    REP(i,Q){
        REP(j,4){
            cout << quei[i][j] << " ";
        }
        cout << endl;
    }*/


    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]);


            l = quei[i][2], r = quei[i][3];
            Di[x][l]++;
            SEGi[x].update(l,Di[x][l]);
            Di[x][r+1]--;
            SEGi[x].update(r,Di[x][r+1]);
        }
    }

    return 0;
}

yukicoder

結果

テストケース

ソースコード