# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
933693 |
2024-02-26T06:03:37 Z |
3mara |
Wall (IOI14_wall) |
C++17 |
|
269 ms |
53840 KB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N=2e6;
int a[N*4];
int add[N*4],rem[N*4];
void upd(int t, int l, int r, int ll, int rr, int op, int val){
if(ll>rr) return;
if(l==ll&&r==rr){
if(op==0) add[t]=max(add[t],val);
else{
if(~rem[t]){
rem[t]=min(rem[t],val);
}
else{
rem[t]=val;
}
}
}
else{
int m=(l+r)/2;
upd(t*2,l,m,ll,min(m,rr),op,val);
upd(t*2+1,m+1,r,max(ll,m+1),rr,op,val);
}
}
int get(int t, int l, int r, int idx){
if(~add[t]){
a[t]=max(add[t],a[t]);
add[t*2]=max(add[t*2],add[t]);
add[t*2+1]=max(add[t*2+1],add[t]);
}
if(~rem[t]){
a[t]=min(rem[t],a[t]);
if(~rem[t*2])rem[t*2]=min(rem[t*2],rem[t]);
else rem[t*2]=rem[t];
if(~rem[t*2+1])rem[t*2+1]=min(rem[t*2+1],rem[t]);
else rem[t*2+1]=rem[t];
}
if(l==r){
return a[t];
}
else{
int m=(l+r)/2;
if(idx<=m) return get(t*2,l,m,idx);
else return get(t*2+1,m+1,r,idx);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
memset(rem,-1,sizeof rem);
for(int i=0;i<k;i++){
upd(1,0,n-1,left[i],right[i],op[i]-1,height[i]);
}
for(int i=0;i<n;i++){
finalHeight[i]=get(1,0,n-1,i);
}
return;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
33368 KB |
Output is correct |
2 |
Incorrect |
6 ms |
33372 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
33368 KB |
Output is correct |
2 |
Correct |
109 ms |
46996 KB |
Output is correct |
3 |
Correct |
102 ms |
39592 KB |
Output is correct |
4 |
Correct |
269 ms |
52708 KB |
Output is correct |
5 |
Correct |
186 ms |
53840 KB |
Output is correct |
6 |
Correct |
179 ms |
52180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
33372 KB |
Output is correct |
2 |
Incorrect |
6 ms |
33372 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
33372 KB |
Output is correct |
2 |
Incorrect |
6 ms |
33596 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |