| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1046965 |
2024-08-07T07:04:14 Z |
김은성(#11022) |
Sweeping (JOI20_sweeping) |
C++17 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
using namespace std;
const int INF = 1234123423;
int x0[1500009], y0[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] = x0[l];
treey[v] = y0[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", &x0[i], &y0[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:4:28: error: 'int y0 [1500009]' redeclared as different kind of entity
4 | int x0[1500009], y0[1500009];
| ^
In file included from /usr/include/features.h:461,
from /usr/include/x86_64-linux-gnu/c++/10/bits/os_defines.h:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/c++config.h:518,
from /usr/include/c++/10/cassert:43,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from sweeping.cpp:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:220:1: note: previous declaration 'double y0(double)'
220 | __MATHCALL (y0,, (_Mdouble_));
| ^~~~~~~~~~
sweeping.cpp: In function 'void settree(int, int, int)':
sweeping.cpp:22:18: warning: pointer to a function used in arithmetic [-Wpointer-arith]
22 | treey[v] = y0[l];
| ^
sweeping.cpp:22:18: error: invalid conversion from 'double (*)(double) noexcept' to 'int' [-fpermissive]
22 | treey[v] = y0[l];
| ~~~~^
| |
| double (*)(double) noexcept
sweeping.cpp: In function 'int main()':
sweeping.cpp:119:31: warning: pointer to a function used in arithmetic [-Wpointer-arith]
119 | scanf("%d %d", &x0[i], &y0[i]);
| ^
sweeping.cpp:119:14: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'double (*)(double) noexcept' [-Wformat=]
119 | scanf("%d %d", &x0[i], &y0[i]);
| ~^ ~~~~~~
| | |
| int* double (*)(double) noexcept
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", &x0[i], &y0[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);
| ~~~~~^~~~~~~~~~~~~~~~~
