結果

問題 No.2421 entersys?
コンテスト
ユーザー HIcoder
提出日時 2023-08-21 13:15:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,521 bytes
コンパイル時間 1,824 ms
コンパイル使用メモリ 130,500 KB
最終ジャッジ日時 2025-02-16 12:02:28
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<numeric>
#include<queue>
#include<cmath>
#include<tuple>
using namespace std;
typedef long long ll;
const ll INF=1LL<<60;
typedef pair<int,int> P;
typedef pair<P,int> PP;
const ll MOD=1e9+7;

struct Query{
    int type;
    string x;
    int t;
    int l;
    int r;

};



int op(int x, int y){
    //(x,y)を比較する任意の演算子.今回はmaxとした
    return (x+y);
}

int e(){
    //initialize value
    return 0;
}


template<class Type,
    Type (*op)(Type,Type),
    Type (*e)()
    > class segment_tree{
    
    public:
        
        std::vector<Type> dat;
        int n=1;
        segment_tree(int n_){    
            while(n < n_){
                n*=2;
            }
            dat = std::vector<Type>(2*n-1,e());// 0,1,2,...,2*n-1,2*n-2
        }

        ~segment_tree(){
            std::vector<Type>().swap(dat);
        }

        void set(int k,Type a){
            update(k,a);
        }


        void update(int k,Type a){
            k+=n-1;
            dat[k] = a;
            while(k>0){
                k = (k-1)/2;
                dat[k]=op(dat[2*k+1],dat[2*k+2]);
            }
        }

        //[a,b)
        Type query(int a,int b,int k,int l,int r){
            if(r<=a || b<=l) return e();
            if(a<=l && r<=b) return dat[k];
            else{

                Type vl = query(a,b,2*k+1,l,(l+r)/2);
                Type vr = query(a,b,2*k+2,(l+r)/2,r);
                return op(vl,vr);
            }
        }

        //[a,b)の範囲でのmax
        Type query(int a,int b){
            return query(a,b,0,0,n);
        }

        Type operator[](int index){
            
            return get(index);
        }

        Type get(int index){
            index += n-1;
            return dat[index];
        }


        void add(int k,Type a){
            Type c=get(k);
            update(k,c+a);
        }
};



struct LazySegmentTree {
private:
    int n;
    vector<ll> node, lazy;

public:
    LazySegmentTree(vector<ll> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }

    //k番目のノードについて遅延評価を行う
    void eval(int k, int l, int r) {
        //遅延配列が空でない場合　自分のノード及び子ノードへの値の伝播が起こる
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {//[l,r)
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;//伝播が終わったので自分のノードの遅延配列を0にする
        }
    }

    //[l,r)かな
    void add(int a, int b, ll x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        //k番目のノードに対して遅延評価を行う
        eval(k, l, r);
        if(b <= l || r <= a) return;//範囲外なら何もしない

        //完全に被覆しているならば,遅延配列に値を入れた後に評価
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {//そうでないならば　子ノードの値を再帰的に計算しえ計算済みの値をもらってくる
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }

    ll getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);//関数が呼び出されたら評価する
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
};



int main(){
    int N;
    cin>>N;

    vector<PP> people;
    //map<string,pair<double,double>> mp;
    map<string,P> mp;

    vector<int> ranges;

    for(int i=0;i<N;i++){
        string x;
        int l,r;
        cin>>x>>l>>r;
        mp[x]={l,r};
       
        ranges.push_back(l);
        ranges.push_back(r);


    }
    int Q;
    cin>>Q;

    vector<Query> queries(Q);

     for(int q=0;q<Q;q++){
        int type;
        cin>>type;
        if(type==1){
            string x;
            int t;
            cin>>x>>t;

            queries[q].type=1;
            queries[q].x=x;
            queries[q].t=t;

        }else if(type==2){
            int t;
            cin>>t;

            queries[q].type=2;
            queries[q].t=t;

            ranges.push_back(t);


        }else{
            //type=3
            string x;
            int l,r;
            cin>>x>>l>>r;


            queries[q].type=3;
            queries[q].x=x;
            queries[q].l=l;
            queries[q].r=r;


            ranges.push_back(l);
            ranges.push_back(r);

        }
    }

    set<int> st(ranges.begin(),ranges.end());

    map<int,int> compress;
    int sz=1;
    for(int v:st){
        compress[v]=sz;
        sz++;
    }


    //segment_tree<int,op,e> seg(sz+3);
    
    LazySegmentTree seg(vector<ll>(sz+3,0));

    for(auto [x,p]:mp){
        auto [l,r]=p;

        seg.add(compress[l],compress[r]+1,1);

        //seg.add(compress[l],1);
        //seg.add(compress[r]+1,-1);



    }



    for(int q=0;q<Q;q++){
        
        if(queries[q].type==1){
            string x=queries[q].x;
            int t=queries[q].t;

            if(!mp.count(x)){
                cout<<"No"<<endl;
            }else{ 

                auto [l,r]=mp[x];
                if(l<=t && t<=r){
                    cout<<"Yes"<<endl;
                }else{
                    cout<<"No"<<endl;
                }
            }

        }else if(queries[q].type==2){
           
            int t=queries[q].t;

            //int ans=seg.query(0,t+1)-seg.query(0,t);
            int ans=seg.getsum(compress[t],compress[t]+1);
            cout<<ans<<endl;

        }else{
            //type=3
         
            string x=queries[q].x;
            int l=queries[q].l;
            int r=queries[q].r;

            //seg.add(compress[l],1);
            //seg.add(compress[r]+1,-1);

            //seg.add(l,r+1,1);
            seg.add(compress[l],compress[r]+1,1);


            mp[x]={l,r};

        }
    }


}
0