| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1046966 |
2024-08-07T07:05:21 Z |
김은성(#11022) |
Sweeping (JOI20_sweeping) |
C++17 |
|
1383 ms |
43196 KB |
#include <bits/stdc++.h>
using namespace std;
const int INF = 1234123423;
int x00[1500009], y00[1500009];
int treex[1<<22], treey[1<<22], lazyx[1<<22], lazyy[1<<22]; //max value stored for x, max value for y
int ansx[1500009], ansy[1500009];
void dolazy(int v, bool op){
treex[v] = max(lazyx[v], treex[v]);
treey[v] = max(lazyy[v], treey[v]);
if(!op){
lazyx[2*v] = max(lazyx[2*v], lazyx[v]);
lazyx[2*v+1] = max(lazyx[2*v+1], lazyx[v]);
lazyy[2*v] = max(lazyy[2*v], lazyy[v]);
lazyy[2*v+1] = max(lazyy[2*v+1], lazyy[v]);
}
lazyx[v] = 0;
lazyy[v] = 0;
}
void settree(int v, int l, int r){
if(l==r){
treex[v] = x00[l];
treey[v] = y00[l];
lazyx[v] = 0;
lazyy[v] = 0;
}
else{
int mid = (l+r)/2;
settree(2*v, l, mid);
settree(2*v+1, mid+1, r);
treex[v] = max(treex[2*v], treex[2*v+1]);
treey[v] = max(treey[2*v], treey[2*v+1]);
lazyx[v] = 0;
lazyy[v] = 0;
}
}
int boundx(int v, int l, int r, int crit){ //maximum i such that x[i] <= crit
if(l==r){
if(treex[v] > crit)
return l-1;
return l;
}
int mid = (l+r)/2;
dolazy(v, l==r);
dolazy(2*v, l==mid);
dolazy(2*v+1, mid+1==r);
if(treex[2*v] <= crit)
return boundx(2*v+1, mid+1, r, crit);
return boundx(2*v, l, mid, crit);
}
int boundy(int v, int l, int r, int crit){ //minimum i such that y[i] <= crit
if(l==r){
if(treey[v] > crit)
return l+1;
return l;
}
int mid = (l+r)/2;
dolazy(v, l==r);
dolazy(2*v, l==mid);
dolazy(2*v+1, mid+1==r);
if(treey[2*v+1] <= crit)
return boundy(2*v, l, mid, crit);
return boundy(2*v+1, mid+1, r, crit);
}
void updatex(int v, int l, int r, int s, int e, int val){
dolazy(v, l==r);
if(e<l || r<s)
return;
if(s<=l && r<=e){
treex[v] = max(treex[v], val);
if(l != r){
lazyx[2*v] = max(lazyx[2*v], val);
lazyx[2*v+1] = max(lazyx[2*v+1], val);
}
return;
}
int mid = (l+r)/2;
updatex(2*v, l, mid, s,e, val);
updatex(2*v+1, mid+1, r, s, e, val);
treex[v] = max(treex[2*v], treex[2*v+1]);
treey[v] = max(treey[2*v], treey[2*v+1]);
}
void updatey(int v, int l, int r, int s, int e, int val){
dolazy(v, l==r);
if(e<l || r<s)
return;
if(s<=l && r<=e){
treey[v] = max(treey[v], val);
if(l != r){
lazyy[2*v] = max(lazyy[2*v], val);
lazyy[2*v+1] = max(lazyy[2*v+1], val);
}
return;
}
int mid = (l+r)/2;
updatey(2*v, l, mid, s, e, val);
updatey(2*v+1, mid+1, r, s, e, val);
treex[v] = max(treex[2*v], treex[2*v+1]);
treey[v] = max(treey[2*v], treey[2*v+1]);
}
pair<int, int> solve(int v, int l, int r, int p){
dolazy(v, l==r);
if(l==r){
return make_pair(treex[v],treey[v]);
}
int mid = (l+r)/2;
pair<int, int> ans;
if(p <= mid)
ans = solve(2*v, l, mid, p);
else
ans = solve(2*v+1, mid+1, r, p);
treex[v] = max(treex[2*v], treex[2*v+1]);
treey[v] = max(treey[2*v], treey[2*v+1]);
return ans;
}
int main(){
int n, m, q, i, j, t, p, l, a, b;
scanf("%d %d %d", &n, &m, &q);
for(i=1; i<=m; i++){
scanf("%d %d", &x00[i], &y00[i]);
}
settree(1, 1, m);
for(i=0; i<q; i++){
scanf("%d", &t);
if(t==1){
scanf("%d", &p);
pair<int, int> res = solve(1, 1, m, p);
printf("%d %d\n", res.first, res.second);
}
else if(t==3){
scanf("%d", &l);
//printf("bound=%d\n", boundx(1, 1, m, l));
updatey(1, 1, m, 1, boundx(1, 1, m, l), n-l);
}
else if(t==2){
scanf("%d", &l);
//printf("bound=%d\n", boundy(1, 1, m, l));
updatex(1, 1, m, boundy(1, 1, m, l), m, n-l);
}
else{
scanf("%d %d", &a, &b);
}
}
return 0;
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:116:18: warning: unused variable 'j' [-Wunused-variable]
116 | int n, m, q, i, j, t, p, l, a, b;
| ^
sweeping.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | scanf("%d %d", &x00[i], &y00[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | scanf("%d", &t);
| ~~~~~^~~~~~~~~~
sweeping.cpp:125:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | scanf("%d", &p);
| ~~~~~^~~~~~~~~~
sweeping.cpp:130:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | scanf("%d", &l);
| ~~~~~^~~~~~~~~~
sweeping.cpp:135:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
135 | scanf("%d", &l);
| ~~~~~^~~~~~~~~~
sweeping.cpp:140:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
140 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1132 ms |
43180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
948 ms |
43196 KB |
Output is correct |
| 2 |
Correct |
962 ms |
43088 KB |
Output is correct |
| 3 |
Correct |
968 ms |
42496 KB |
Output is correct |
| 4 |
Correct |
954 ms |
43048 KB |
Output is correct |
| 5 |
Correct |
981 ms |
43092 KB |
Output is correct |
| 6 |
Correct |
919 ms |
43004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
948 ms |
43196 KB |
Output is correct |
| 2 |
Correct |
962 ms |
43088 KB |
Output is correct |
| 3 |
Correct |
968 ms |
42496 KB |
Output is correct |
| 4 |
Correct |
954 ms |
43048 KB |
Output is correct |
| 5 |
Correct |
981 ms |
43092 KB |
Output is correct |
| 6 |
Correct |
919 ms |
43004 KB |
Output is correct |
| 7 |
Incorrect |
1383 ms |
42940 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
