| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 828152 |
2023-08-17T06:05:44 Z |
반딧불(#10380) |
Curtains (NOI23_curtains) |
C++17 |
|
14 ms |
23828 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
int treeMin[1<<20], treeMax[1<<20], lazy[1<<20];
void init(int i, int l, int r){
treeMin[i] = l, treeMax[i] = r;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void propagate(int i, int l, int r){
if(!lazy[i]) return;
treeMin[i] = max(treeMin[i], lazy[i]);
treeMax[i] = max(treeMax[i], lazy[i]);
if(l!=r){
lazy[i*2] = max(lazy[i*2], lazy[i]);
lazy[i*2+1] = max(lazy[i*2+1], lazy[i]);
}
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, int x){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] = x;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, x);
update(i*2+1, m+1, r, s, e, x);
treeMax[i] = max(treeMax[i*2], treeMax[i*2+1]);
treeMin[i] = min(treeMin[i*2], treeMin[i*2+1]);
}
int query(int i, int l, int r, int x){
propagate(i, l, r);
if(l==r) return treeMax[i];
int m = (l+r)>>1;
if(x<=m) return query(i*2, l, m, x);
else return query(i*2+1, m+1, r, x);
}
int atLeast(int i, int l, int r, int x){
if(l==r) return l;
int m = (l+r)>>1;
if(treeMax[i*2] >= x) return atLeast(i*2, l, m, x);
else return atLeast(i*2+1, m+1, r, x);
}
} tree;
int n, k, q;
vector<int> vec[500002];
vector<pair<int, int> > queries[500002];
int ans[500002];
int main(){
scanf("%d %d %d", &n, &k, &q);
for(int i=1; i<=k; i++){
int l, r;
scanf("%d %d", &l, &r);
vec[r].push_back(l);
}
for(int i=1; i<=q; i++){
int l, r;
scanf("%d %d", &l, &r);
queries[r].push_back(make_pair(l, i));
}
tree.init(1, 0, n);
for(int i=1; i<=n; i++){
for(int x: vec[i]){
int y = tree.atLeast(1, 0, n, x-1);
tree.update(1, 1, n, y, i, i);
//printf("Updated %d to %d\n", y, i);
}
for(pair<int, int> p: queries[i]){
int v = tree.query(1, 0, n, p.first-1);
ans[p.second] = v == i;
}
}
for(int i=1; i<=q; i++) printf("%s\n", ans[i] ? "YES" : "NO");
}
Compilation message
curtains.cpp: In function 'int main()':
curtains.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d %d %d", &n, &k, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%d %d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~
curtains.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d %d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
23828 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
23716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23776 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
