oj.uz

Submission #955912

# Submission time Handle Problem Language Result Execution time Memory
955912 2024-03-31T17:16:49 Z NemanjaSo2005 Curtains (NOI23_curtains) C++17
100 / 100
 832 ms 70480 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26968 KB Output is correct
2 Correct 8 ms 27084 KB Output is correct
3 Correct 7 ms 27224 KB Output is correct
4 Correct 6 ms 26972 KB Output is correct
5 Correct 6 ms 26972 KB Output is correct
6 Correct 6 ms 26968 KB Output is correct
7 Correct 6 ms 26968 KB Output is correct
8 Correct 7 ms 26972 KB Output is correct
9 Correct 6 ms 26972 KB Output is correct
10 Correct 6 ms 27108 KB Output is correct
11 Correct 6 ms 27092 KB Output is correct
12 Correct 6 ms 26972 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26968 KB Output is correct
2 Correct 8 ms 27084 KB Output is correct
3 Correct 7 ms 27224 KB Output is correct
4 Correct 6 ms 26972 KB Output is correct
5 Correct 6 ms 26972 KB Output is correct
6 Correct 6 ms 26968 KB Output is correct
7 Correct 6 ms 26968 KB Output is correct
8 Correct 7 ms 26972 KB Output is correct
9 Correct 6 ms 26972 KB Output is correct
10 Correct 6 ms 27108 KB Output is correct
11 Correct 6 ms 27092 KB Output is correct
12 Correct 6 ms 26972 KB Output is correct
13 Correct 7 ms 27224 KB Output is correct
14 Correct 7 ms 27228 KB Output is correct
15 Correct 8 ms 27272 KB Output is correct
16 Correct 8 ms 27228 KB Output is correct
17 Correct 7 ms 27228 KB Output is correct
18 Correct 7 ms 27208 KB Output is correct
19 Correct 7 ms 27228 KB Output is correct
20 Correct 7 ms 27224 KB Output is correct
21 Correct 8 ms 27224 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26968 KB Output is correct
2 Correct 8 ms 27084 KB Output is correct
3 Correct 7 ms 27224 KB Output is correct
4 Correct 6 ms 26972 KB Output is correct
5 Correct 6 ms 26972 KB Output is correct
6 Correct 6 ms 26968 KB Output is correct
7 Correct 6 ms 26968 KB Output is correct
8 Correct 7 ms 26972 KB Output is correct
9 Correct 6 ms 26972 KB Output is correct
10 Correct 6 ms 27108 KB Output is correct
11 Correct 6 ms 27092 KB Output is correct
12 Correct 6 ms 26972 KB Output is correct
13 Correct 7 ms 27224 KB Output is correct
14 Correct 7 ms 27228 KB Output is correct
15 Correct 8 ms 27272 KB Output is correct
16 Correct 8 ms 27228 KB Output is correct
17 Correct 7 ms 27228 KB Output is correct
18 Correct 7 ms 27208 KB Output is correct
19 Correct 7 ms 27228 KB Output is correct
20 Correct 7 ms 27224 KB Output is correct
21 Correct 8 ms 27224 KB Output is correct
22 Correct 150 ms 38484 KB Output is correct
23 Correct 155 ms 38992 KB Output is correct
24 Correct 188 ms 40016 KB Output is correct
25 Correct 310 ms 43992 KB Output is correct
26 Correct 154 ms 38904 KB Output is correct
27 Correct 311 ms 43908 KB Output is correct
28 Correct 311 ms 44052 KB Output is correct
29 Correct 145 ms 38008 KB Output is correct
30 Correct 103 ms 38192 KB Output is correct
31 Correct 114 ms 38992 KB Output is correct
32 Correct 264 ms 43536 KB Output is correct
33 Correct 97 ms 38484 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26972 KB Output is correct
2 Correct 6 ms 26972 KB Output is correct
3 Correct 6 ms 27220 KB Output is correct
4 Correct 6 ms 26968 KB Output is correct
5 Correct 8 ms 27580 KB Output is correct
6 Correct 7 ms 27228 KB Output is correct
7 Correct 7 ms 27480 KB Output is correct
8 Correct 100 ms 38228 KB Output is correct
9 Correct 112 ms 38992 KB Output is correct
10 Correct 262 ms 43332 KB Output is correct
11 Correct 106 ms 38480 KB Output is correct
12 Correct 97 ms 36688 KB Output is correct
13 Correct 98 ms 36628 KB Output is correct
14 Correct 83 ms 36816 KB Output is correct
15 Correct 77 ms 36264 KB Output is correct
16 Correct 77 ms 36696 KB Output is correct
17 Correct 79 ms 36436 KB Output is correct
18 Correct 654 ms 69708 KB Output is correct
19 Correct 676 ms 69572 KB Output is correct
20 Correct 530 ms 70228 KB Output is correct
21 Correct 546 ms 69636 KB Output is correct
22 Correct 530 ms 68656 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26968 KB Output is correct
2 Correct 8 ms 27084 KB Output is correct
3 Correct 7 ms 27224 KB Output is correct
4 Correct 6 ms 26972 KB Output is correct
5 Correct 6 ms 26972 KB Output is correct
6 Correct 6 ms 26968 KB Output is correct
7 Correct 6 ms 26968 KB Output is correct
8 Correct 7 ms 26972 KB Output is correct
9 Correct 6 ms 26972 KB Output is correct
10 Correct 6 ms 27108 KB Output is correct
11 Correct 6 ms 27092 KB Output is correct
12 Correct 6 ms 26972 KB Output is correct
13 Correct 7 ms 27224 KB Output is correct
14 Correct 7 ms 27228 KB Output is correct
15 Correct 8 ms 27272 KB Output is correct
16 Correct 8 ms 27228 KB Output is correct
17 Correct 7 ms 27228 KB Output is correct
18 Correct 7 ms 27208 KB Output is correct
19 Correct 7 ms 27228 KB Output is correct
20 Correct 7 ms 27224 KB Output is correct
21 Correct 8 ms 27224 KB Output is correct
22 Correct 83 ms 32596 KB Output is correct
23 Correct 86 ms 32548 KB Output is correct
24 Correct 111 ms 35332 KB Output is correct
25 Correct 115 ms 35204 KB Output is correct
26 Correct 94 ms 36672 KB Output is correct
27 Correct 92 ms 36708 KB Output is correct
28 Correct 74 ms 34644 KB Output is correct
29 Correct 90 ms 36188 KB Output is correct
30 Correct 111 ms 35136 KB Output is correct
31 Correct 109 ms 35308 KB Output is correct
32 Correct 101 ms 35668 KB Output is correct
33 Correct 99 ms 36432 KB Output is correct
34 Correct 114 ms 35152 KB Output is correct
35 Correct 111 ms 34924 KB Output is correct
36 Correct 101 ms 35688 KB Output is correct
37 Correct 97 ms 36480 KB Output is correct
38 Correct 100 ms 36648 KB Output is correct
39 Correct 76 ms 36688 KB Output is correct
40 Correct 75 ms 36432 KB Output is correct
41 Correct 77 ms 36692 KB Output is correct
42 Correct 76 ms 36432 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26968 KB Output is correct
2 Correct 8 ms 27084 KB Output is correct
3 Correct 7 ms 27224 KB Output is correct
4 Correct 6 ms 26972 KB Output is correct
5 Correct 6 ms 26972 KB Output is correct
6 Correct 6 ms 26968 KB Output is correct
7 Correct 6 ms 26968 KB Output is correct
8 Correct 7 ms 26972 KB Output is correct
9 Correct 6 ms 26972 KB Output is correct
10 Correct 6 ms 27108 KB Output is correct
11 Correct 6 ms 27092 KB Output is correct
12 Correct 6 ms 26972 KB Output is correct
13 Correct 7 ms 27224 KB Output is correct
14 Correct 7 ms 27228 KB Output is correct
15 Correct 8 ms 27272 KB Output is correct
16 Correct 8 ms 27228 KB Output is correct
17 Correct 7 ms 27228 KB Output is correct
18 Correct 7 ms 27208 KB Output is correct
19 Correct 7 ms 27228 KB Output is correct
20 Correct 7 ms 27224 KB Output is correct
21 Correct 8 ms 27224 KB Output is correct
22 Correct 150 ms 38484 KB Output is correct
23 Correct 155 ms 38992 KB Output is correct
24 Correct 188 ms 40016 KB Output is correct
25 Correct 310 ms 43992 KB Output is correct
26 Correct 154 ms 38904 KB Output is correct
27 Correct 311 ms 43908 KB Output is correct
28 Correct 311 ms 44052 KB Output is correct
29 Correct 145 ms 38008 KB Output is correct
30 Correct 103 ms 38192 KB Output is correct
31 Correct 114 ms 38992 KB Output is correct
32 Correct 264 ms 43536 KB Output is correct
33 Correct 97 ms 38484 KB Output is correct
34 Correct 6 ms 26972 KB Output is correct
35 Correct 6 ms 26972 KB Output is correct
36 Correct 6 ms 27220 KB Output is correct
37 Correct 6 ms 26968 KB Output is correct
38 Correct 8 ms 27580 KB Output is correct
39 Correct 7 ms 27228 KB Output is correct
40 Correct 7 ms 27480 KB Output is correct
41 Correct 100 ms 38228 KB Output is correct
42 Correct 112 ms 38992 KB Output is correct
43 Correct 262 ms 43332 KB Output is correct
44 Correct 106 ms 38480 KB Output is correct
45 Correct 97 ms 36688 KB Output is correct
46 Correct 98 ms 36628 KB Output is correct
47 Correct 83 ms 36816 KB Output is correct
48 Correct 77 ms 36264 KB Output is correct
49 Correct 77 ms 36696 KB Output is correct
50 Correct 79 ms 36436 KB Output is correct
51 Correct 654 ms 69708 KB Output is correct
52 Correct 676 ms 69572 KB Output is correct
53 Correct 530 ms 70228 KB Output is correct
54 Correct 546 ms 69636 KB Output is correct
55 Correct 530 ms 68656 KB Output is correct
56 Correct 83 ms 32596 KB Output is correct
57 Correct 86 ms 32548 KB Output is correct
58 Correct 111 ms 35332 KB Output is correct
59 Correct 115 ms 35204 KB Output is correct
60 Correct 94 ms 36672 KB Output is correct
61 Correct 92 ms 36708 KB Output is correct
62 Correct 74 ms 34644 KB Output is correct
63 Correct 90 ms 36188 KB Output is correct
64 Correct 111 ms 35136 KB Output is correct
65 Correct 109 ms 35308 KB Output is correct
66 Correct 101 ms 35668 KB Output is correct
67 Correct 99 ms 36432 KB Output is correct
68 Correct 114 ms 35152 KB Output is correct
69 Correct 111 ms 34924 KB Output is correct
70 Correct 101 ms 35688 KB Output is correct
71 Correct 97 ms 36480 KB Output is correct
72 Correct 100 ms 36648 KB Output is correct
73 Correct 76 ms 36688 KB Output is correct
74 Correct 75 ms 36432 KB Output is correct
75 Correct 77 ms 36692 KB Output is correct
76 Correct 76 ms 36432 KB Output is correct
77 Correct 789 ms 64360 KB Output is correct
78 Correct 770 ms 64100 KB Output is correct
79 Correct 694 ms 70480 KB Output is correct
80 Correct 661 ms 70480 KB Output is correct
81 Correct 648 ms 68524 KB Output is correct
82 Correct 651 ms 69460 KB Output is correct
83 Correct 832 ms 64212 KB Output is correct
84 Correct 770 ms 64048 KB Output is correct
85 Correct 746 ms 65928 KB Output is correct
86 Correct 681 ms 61708 KB Output is correct
87 Correct 704 ms 62196 KB Output is correct
88 Correct 704 ms 68088 KB Output is correct