結果

問題 No.2421 entersys?
コンテスト
ユーザー maple_1016
提出日時 2023-08-12 16:01:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 3,657 bytes
コンパイル時間 3,602 ms
コンパイル使用メモリ 226,028 KB
実行使用メモリ 63,664 KB
最終ジャッジ日時 2024-11-20 04:56:54
合計ジャッジ時間 25,502 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 RE * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define reps(i,n) for(ll i=1;i<=(n);++i)
#define repr(i,n) for(ll i=2;i*i<=(n);++i)
#define ll long long
#define all(x) (x).begin(),(x).end()
#define sz(x) ((string)(x).size())
#define pb push_back
#define pob pop_back()
#define MMod (ll)1000000007
#define mmod (ll)998244353
#define setp(x) setprecision((ll)(x))
#define INF (ll)(1000000000000000000)
#define mp make_pair
using namespace std;
using pii=pair<int, int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vc=vector<char>;
using vb=vector<bool>;
using vl=vector<long long>;
using vvi=vector<vi>;
using vvl=vector<vl>;
using vvc=vector<vc>;
using vvb=vector<vb>;
using vpi=vector<pii>;
using vpl=vector<pair<ll,ll>>;
using vs=vector<string>;
using pqi=priority_queue<int>;
vpi fs={mp(1,0),mp(-1,0),mp(0,1),mp(0,-1)};

struct segment{
    vector<ll> value;
    int N;
    segment(int n){
        N=1;
        while(N<n){
            N*=2;
        }
        value.resize(N*2);
        for(int i=0;i<N*2;i++){
            value[i]=0;
        }
    }
    void updata(int i,ll x){
        i+=N-1;
        value[i]+=x;
        while(i>0){
            i=(i-1)/2;
            value[i]=(value[i*2+1]+value[i*2+2]);
        }
    }
    ll quety(int a,ll b,int k,int l,int r){
        if(r<=a||b<=l){
            return(0);
        }
        if(a<=l&&r<=b){
            return(value[k]);
        }else{
            ll c1=quety(a,b,2*k+1,l,(l+r)/2);
            ll c2=quety(a,b,2*k+2,(l+r)/2,r);
            return(c1+c2);
        }
    }
    ll get(int a,ll b){
        return(quety(a,b+1,0,0,N));
    }
};

int main(){
  int n; cin>>n;
  int k=1;
  segment seg(5e5+10);
  map<string,int> aa;
  vector<vector<pii>> p(5e5+100);
  vpi pp;
  vi ppp;
  rep(i,n){
    string a; cin>>a;
    int b,c; cin>>b>>c;
    if(aa[a]==0){
      aa[a]=k;
      k++;
    } 
    p[aa[a]].pb(mp(b,c));
    pp.pb(mp(b,c));
    ppp.pb(b);
    ppp.pb(c);
  }
  int qq; cin>>qq;
  vvi q(qq,vi(3));
  map<int,string> ss;
  rep(i,qq){
    cin>>q[i][0];
    if(q[i][0]==1) {
      string v; cin>>v;
      cin>>q[i][1];
      ss[i]=v;
    } else if(q[i][0]==2) {
      cin>>q[i][1];
      ppp.pb(q[i][1]);
    } else if(q[i][0]==3) {
      string v; cin>>v;
      ss[i]=v;
      cin>>q[i][1]>>q[i][2];
      ppp.pb(q[i][1]);
      ppp.pb(q[i][2]);
    }
  }
  int jj=1;
  map<int,int> aaa;
  sort(all(ppp));
  rep(i,ppp.size()){
    if(aaa[ppp[i]]==0){
      aaa[ppp[i]]=jj;
      jj++;
    }
  }
  rep(i,pp.size()){
    int g=aaa[pp[i].first],h=aaa[pp[i].second];
    seg.updata(g,1);
    seg.updata(h+1,-1);
  }
  vi d(2e5+10,0);
  rep(i,qq){
    int c=q[i][0];
    if(c==1){
      string s=ss[i];
      int t=q[i][1];
      if(aa[s]==0) {
        aa[s]=k;
        k++;
        cout<<"No"<<endl;
        continue;
      }
      int kk=aa[s];
      if(d[kk]==0) {
        sort(all(p[kk]));
        d[kk]=1;
      }
      int ok=0,ng=p[kk].size();
      if(p[kk][0].first>t){
        cout<<"No"<<endl;
        continue;
      }
      while(ng-ok>1){
        int j=(ok+ng)/2;
        if(p[kk][j].first>t) ng=t;
        else ok=t;
      }
      if(p[kk][ok].second>=t) cout<<"Yes"<<endl;
      else cout<<"No"<<endl;
    } else if(c==2){
      int t=aaa[q[i][1]];
      cout<<seg.get(0,t)<<endl;
    } else if(c==3){
      string s=ss[i];
      int xx=q[i][1],yy=q[i][2];
      int x=aaa[q[i][1]],y=aaa[q[i][2]];
      if(aa[s]==0){
        aa[s]=k;
        k++;
      } 
      p[aa[s]].pb(mp(xx,yy));
      d[aa[s]]=0;
      seg.updata(x,1);
      seg.updata(y+1,-1);
    }
  }
}
0