| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 960604 |
2024-04-10T16:47:48 Z |
kim |
Wall (IOI14_wall) |
C++17 |
|
877 ms |
17544 KB |
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
struct segment{
int a[1<<20],lz[1<<20][2],l0,r0;
bitset<1<<20> b;
void build(int i,int il,int ir){
lz[i][0]=lz[i][1]=-1;
if(il==ir) return;
int im=il+ir>>1;
build(i<<1,il,im), build(i<<1|1,im+1,ir);
}
void init(int l,int r){
l0=l,r0=r;
build(1,l,r);
}
void flush(int i,int il,int ir){
bool op=!b[i];
if(lz[i][op]!=-1){
if(il!=ir){
if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
}
else{
if(op==0) a[i]=max(a[i],lz[i][op]);
else a[i]=min(a[i],lz[i][op]);
}
lz[i][op]=-1;
}
op^=1;
if(lz[i][op]!=-1){
if(il!=ir){
if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
}
else{
if(op==0) a[i]=max(a[i],lz[i][op]);
else a[i]=min(a[i],lz[i][op]);
}
lz[i][op]=-1;
}
}
void upd(int i,int il,int ir,int l,int r,int op,int v){
flush(i,il,ir);
if(l<=il&&ir<=r){
if(lz[i][op]==-1 || op==0&&lz[i][op]<v || op==1&&lz[i][op]>v) lz[i][op]=v, b[i]=op, flush(i,il,ir);
return;
}
if(il>r||ir<l) return;
int im=il+ir>>1;
upd(i<<1,il,im,l,r,op,v), upd(i<<1|1,im+1,ir,l,r,op,v);
}
void upd(int l,int r,int op,int v){upd(1,l0,r0,l,r,op,v);}
int qr(int i,int il,int ir,int x){
flush(i,il,ir);
if(il==ir) return a[i];
int im=il+ir>>1;
if(x<=im) return qr(i<<1,il,im,x);
return qr(i<<1|1,im+1,ir,x);
}
int qr(int i){return qr(1,l0,r0,i);}
}t;
void buildWall(int n, int k, int op[], int L[], int R[], int H[], int ans[]){
vector<int> comp;
for(int i=0;i<k;++i) comp.eb(L[i]),comp.eb(++R[i]);
comp.eb(0),comp.eb(n);
sort(comp.begin(),comp.end());
comp.erase(unique(comp.begin(),comp.end()),comp.end());
t.init(0,comp.size());
for(int i=0;i<k;++i){
L[i]=lower_bound(comp.begin(),comp.end(),L[i])-comp.begin();
R[i]=lower_bound(comp.begin(),comp.end(),R[i])-comp.begin()-1;
t.upd(L[i],R[i],op[i]-1,H[i]);
}
for(int i=0,j=0;i+1<comp.size();++i){
for(;j<comp[i+1];++j) ans[j]=t.qr(i);
}
}
Compilation message
wall.cpp: In member function 'void segment::build(int, int, int)':
wall.cpp:12:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
12 | int im=il+ir>>1;
| ~~^~~
wall.cpp: In member function 'void segment::flush(int, int, int)':
wall.cpp:23:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
23 | if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:23:66: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
23 | if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:24:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
24 | if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:24:70: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
24 | if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:35:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
35 | if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:35:66: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
35 | if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op], b[i<<1]=op;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:36:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
36 | if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:36:70: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
36 | if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op], b[i<<1|1]=op;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp: In member function 'void segment::upd(int, int, int, int, int, int, int)':
wall.cpp:48:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
48 | if(lz[i][op]==-1 || op==0&&lz[i][op]<v || op==1&&lz[i][op]>v) lz[i][op]=v, b[i]=op, flush(i,il,ir);
| ~~~~~^~~~~~~~~~~~~
wall.cpp:48:51: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
48 | if(lz[i][op]==-1 || op==0&&lz[i][op]<v || op==1&&lz[i][op]>v) lz[i][op]=v, b[i]=op, flush(i,il,ir);
| ~~~~~^~~~~~~~~~~~~
wall.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int im=il+ir>>1;
| ~~^~~
wall.cpp: In member function 'int segment::qr(int, int, int, int)':
wall.cpp:59:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | int im=il+ir>>1;
| ~~^~~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i=0,j=0;i+1<comp.size();++i){
| ~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
2684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
135 ms |
14316 KB |
Output is correct |
| 3 |
Correct |
296 ms |
9844 KB |
Output is correct |
| 4 |
Correct |
877 ms |
17544 KB |
Output is correct |
| 5 |
Correct |
363 ms |
17328 KB |
Output is correct |
| 6 |
Correct |
316 ms |
17084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
2652 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
2652 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
