Submission #955912

#	Time	Username	Problem	Language	Result	Execution time	Memory
955912		NemanjaSo2005	Curtains (NOI23_curtains)	C++17	100 / 100	832 ms	70480 KiB

curtains

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5e5+5;
int N,M,Q,st[4*maxn],lazy[4*maxn],K;
vector<int> koji[maxn],L[maxn];
struct upit{
   int l,r;
   bool ans;
} upiti[maxn];
void prop(int gde){
   st[gde*2]=max(st[gde*2],lazy[gde]);
   lazy[gde*2]=max(lazy[gde*2],lazy[gde]);
   st[gde*2+1]=max(st[gde*2+1],lazy[gde]);
   lazy[gde*2+1]=max(lazy[gde*2+1],lazy[gde]);
   return;
}
void update(int lg,int dg,int kol,int gde=1,int lc=1,int dc=K){
   if(lg==lc and dg==dc){
      lazy[gde]=max(lazy[gde],kol);
      st[gde]=max(st[gde],kol);
      return;
   }
   prop(gde);
   int sred=(lc+dc)/2;
   if(dg<=sred)
      update(lg,dg,kol,gde*2,lc,sred);
   else if(lg>sred)
      update(lg,dg,kol,gde*2+1,sred+1,dc);
   else{
      update(lg,sred,kol,gde*2,lc,sred);
      update(sred+1,dg,kol,gde*2+1,sred+1,dc);
   }
   st[gde]=min(st[gde*2],st[gde*2+1]);
   return;
}
int get(int lg,int dg,int gde=1,int lc=1,int dc=K){
   if(lg==lc and dg==dc)
      return st[gde];
   prop(gde);
   int sred=(lc+dc)/2;
   if(dg<=sred)
      return get(lg,dg,gde*2,lc,sred);
   if(lg>sred)
      return get(lg,dg,gde*2+1,sred+1,dc);
   int v1,v2;
   v1=get(lg,sred,gde*2,lc,sred);
   v2=get(sred+1,dg,gde*2+1,sred+1,dc);
   return min(v1,v2);
}
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cin>>N>>M>>Q;
   K=1;
   while(K<N)
      K<<=1;
   while(M--){
      int l,r;
      cin>>l>>r;
      L[r].push_back(l);
   }
   for(int i=1;i<=Q;i++){
      cin>>upiti[i].l>>upiti[i].r;
      koji[upiti[i].r].push_back(i);
   }
   for(int i=1;i<=N;i++){
      for(int x:L[i])
         update(x,i,x);
      for(int id:koji[i]){
         int a=upiti[id].l;
         int b=upiti[id].r;
         if(get(a,b)==a)
            upiti[id].ans=1;
         else
            upiti[id].ans=0;
      }
   }
   for(int i=1;i<=Q;i++)
      if(upiti[i].ans)
         cout<<"YES\n";
      else
         cout<<"NO\n";
   return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36
• Subtask 6: 20 / 20