Submission #1146178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146178		Ak_16	Curtains (NOI23_curtains)	C++20	20 / 100	684 ms	7960 KiB

curtains

#include <iostream>
using namespace std;

const int MAXN = 500005;
int segt[2 * MAXN];
int n;

void build() {
    for (int i = n - 1; i > 0; --i) {
        segt[i] = max(segt[2 * i], segt[2 * i + 1]);
    }
}

void update(int pos, int value) {
    pos += n - 1;
    segt[pos] = value;
    for (int i=pos/2; i>=1; i/=2) {
        segt[i] = max(segt[2 * i], segt[2 * i + 1]);
    }
}

int query(int l, int r) {
    l += n - 1;
    r += n - 1;
    int sum = 0;
    while (l <= r) {
        if (l % 2 == 1) sum = max(sum,  segt[l]); l++;
        if (r % 2 == 0) sum = max(sum,  segt[r]); r--;
        l /= 2;
        r /= 2;
    }
    return sum;
}

int main() {
    int m,q;
    int be[500005];
    int l1,r1;
   
    cin>>n>>m>>q;
    
    for(int i=n; i<2*n; i++){segt[i] = 0;}
    
    
    for(int i=1; i<=n; i++){ be[i] = 100000000;}
    
    
    for(int i=1; i<=m; i++){
      cin>>l1>>r1;
      be[r1] = min(be[r1], l1);
    }
    
    for(int i=1; i<=n; i++){
      
      if(be[i] == 1){ 
        update(i, 1); 
        }
        
      else if(be[i]<=i) {
        int n1 = query(be[i]-1, i-1);
        update(i, n1);
      }
      
    }
    
    for(int i=1; i<=q; i++){
      int x,y;
      cin>>x>>y;
      if(segt[y+n-1]==1){cout<<"YES"<<endl;}
      else {cout<<"NO"<<endl;}
    }
    
}

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