# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
67905 |
2018-08-15T13:02:45 Z |
edisonhello |
Wall (IOI14_wall) |
C++14 |
|
1074 ms |
263168 KB |
#include<bits/stdc++.h>
using namespace std;
struct node{
node *l,*r;
int mx,mn;
void addtag(int t,int x){
if(t==1)mn=max(mn,x),mx=max(mx,mn);
else mx=min(mx,x),mn=min(mn,mx);
}
void push(){
if(!l)return;
l->addtag(1,mn);
l->addtag(2,mx);
r->addtag(1,mn);
r->addtag(2,mx);
mx=1e9,mn=-1e9;
}
node():l(0),r(0),mx(1e9),mn(-1e9){}
} *root;
int *ans;
#define mid ((l+r)>>1)
void build(node *now,int l,int r){
if(l==r){ return; }
build(now->l=new node(),l,mid);
build(now->r=new node(),mid+1,r);
}
void modify(node *now,int l,int r,int ml,int mr,int t,int x){
if(r<ml || mr<l)return;
now->push();
if(ml<=l&&r<=mr){
now->addtag(t,x);
return;
}
modify(now->l,l,mid,ml,mr,t,x);
modify(now->r,mid+1,r,ml,mr,t,x);
}
void dfs(node *now,int l,int r,int mn,int mx){
mn=max(mn,now->mn); mx=max(mx,now->mx);
now->push();
if(l==r){
if(0<now->mn)ans[l]=now->mn;
else if(0>now->mx)ans[l]=now->mx;
else ans[l]=0;
return;
}
dfs(now->l,l,mid,mn,mx);
dfs(now->r,mid+1,r,mn,mx);
}
void buildWall(int n,int q,int types[],int ls[],int rs[],int hs[],int __ans[]){
ans=__ans;
build(root=new node(),0,n-1);
for(int i=0;i<q;++i){
modify(root,0,n-1,ls[i],rs[i],types[i],hs[i]);
}
dfs(root,0,n-1,-1e9,1e9);
}
#ifdef WEAK
int __o[500005],__l[500005],__r[500005],__h[500005],__ans[2000005];
int main(){
int n; cin>>n;
int q; cin>>q;
for(int i=0;i<q;++i)cin>>__o[i]>>__l[i]>>__r[i]>>__h[i];
buildWall(n,q,__o,__l,__r,__h,__ans);
for(int i=0;i<n;++i)cout<<__ans[i]<<" ";
cout<<endl;
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
5 ms |
512 KB |
Output is correct |
3 |
Correct |
4 ms |
512 KB |
Output is correct |
4 |
Correct |
10 ms |
1456 KB |
Output is correct |
5 |
Correct |
9 ms |
1572 KB |
Output is correct |
6 |
Correct |
8 ms |
1624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1624 KB |
Output is correct |
2 |
Correct |
216 ms |
8768 KB |
Output is correct |
3 |
Correct |
217 ms |
8768 KB |
Output is correct |
4 |
Correct |
729 ms |
25372 KB |
Output is correct |
5 |
Correct |
348 ms |
35952 KB |
Output is correct |
6 |
Correct |
379 ms |
44660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
44660 KB |
Output is correct |
2 |
Correct |
4 ms |
44660 KB |
Output is correct |
3 |
Correct |
3 ms |
44660 KB |
Output is correct |
4 |
Correct |
9 ms |
44660 KB |
Output is correct |
5 |
Correct |
9 ms |
44660 KB |
Output is correct |
6 |
Correct |
13 ms |
44660 KB |
Output is correct |
7 |
Correct |
3 ms |
44660 KB |
Output is correct |
8 |
Correct |
188 ms |
44660 KB |
Output is correct |
9 |
Correct |
239 ms |
44660 KB |
Output is correct |
10 |
Correct |
669 ms |
53944 KB |
Output is correct |
11 |
Correct |
429 ms |
64708 KB |
Output is correct |
12 |
Correct |
357 ms |
73136 KB |
Output is correct |
13 |
Correct |
2 ms |
73136 KB |
Output is correct |
14 |
Correct |
192 ms |
73136 KB |
Output is correct |
15 |
Correct |
43 ms |
73136 KB |
Output is correct |
16 |
Correct |
659 ms |
88892 KB |
Output is correct |
17 |
Correct |
355 ms |
97968 KB |
Output is correct |
18 |
Correct |
458 ms |
107144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
107144 KB |
Output is correct |
2 |
Correct |
5 ms |
107144 KB |
Output is correct |
3 |
Correct |
4 ms |
107144 KB |
Output is correct |
4 |
Correct |
15 ms |
107144 KB |
Output is correct |
5 |
Correct |
8 ms |
107144 KB |
Output is correct |
6 |
Correct |
8 ms |
107144 KB |
Output is correct |
7 |
Correct |
2 ms |
107144 KB |
Output is correct |
8 |
Correct |
195 ms |
107144 KB |
Output is correct |
9 |
Correct |
208 ms |
107144 KB |
Output is correct |
10 |
Correct |
633 ms |
116376 KB |
Output is correct |
11 |
Correct |
338 ms |
127100 KB |
Output is correct |
12 |
Correct |
344 ms |
135796 KB |
Output is correct |
13 |
Correct |
4 ms |
135796 KB |
Output is correct |
14 |
Correct |
212 ms |
135796 KB |
Output is correct |
15 |
Correct |
37 ms |
135796 KB |
Output is correct |
16 |
Correct |
726 ms |
151528 KB |
Output is correct |
17 |
Correct |
366 ms |
160640 KB |
Output is correct |
18 |
Correct |
392 ms |
169532 KB |
Output is correct |
19 |
Runtime error |
1074 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
20 |
Halted |
0 ms |
0 KB |
- |