| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 31811 |
2017-09-09T16:14:16 Z |
top34051 |
Wall (IOI14_wall) |
C++14 |
|
1036 ms |
87968 KB |
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 2000005
int ans[maxn];
int L[maxn*4], R[maxn*4];
void upd(int pos,int l,int r) {
L[pos] = max(L[pos], l);
L[pos] = min(L[pos], r);
R[pos] = max(R[pos], l);
R[pos] = min(R[pos], r);
}
void update(int pos,int l,int r,int x,int y,int val,int type) {
if(l!=r) {
upd(pos<<1,L[pos],R[pos]);
upd(pos<<1|1,L[pos],R[pos]);
}
if(l>r || y<l || r<x) return ;
if(x<=l && r<=y) {
if(type==1) {
L[pos] = max(L[pos], val);
R[pos] = max(R[pos], val);
}
else {
L[pos] = min(L[pos], val);
R[pos] = min(R[pos], val);
}
return ;
}
int mid = (l+r)/2;
update(pos<<1,l,mid,x,y,val,type); update(pos<<1|1,mid+1,r,x,y,val,type);
L[pos] = min(L[pos<<1], L[pos<<1|1]);
R[pos] = max(R[pos<<1], R[pos<<1|1]);
}
void query(int pos,int l,int r) {
if(l!=r) {
upd(pos<<1,L[pos],R[pos]);
upd(pos<<1|1,L[pos],R[pos]);
}
if(l==r) {
ans[l] = L[pos];
return ;
}
int mid = (l+r)/2;
query(pos<<1,l,mid); query(pos<<1|1,mid+1,r);
}
void buildWall(int n, int m, int type[], int l[], int r[], int val[], int ret[]) {
int i;
for(i=0;i<m;i++) update(1,0,n-1,l[i],r[i],val[i],type[i]);
query(1,0,n-1);
for(i=0;i<n;i++) ret[i] = ans[i];
return ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
72328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
72464 KB |
Output is correct |
| 3 |
Correct |
0 ms |
72328 KB |
Output is correct |
| 4 |
Correct |
6 ms |
72464 KB |
Output is correct |
| 5 |
Correct |
3 ms |
72464 KB |
Output is correct |
| 6 |
Correct |
3 ms |
72464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
72328 KB |
Output is correct |
| 2 |
Correct |
153 ms |
80152 KB |
Output is correct |
| 3 |
Correct |
269 ms |
75724 KB |
Output is correct |
| 4 |
Correct |
673 ms |
80544 KB |
Output is correct |
| 5 |
Correct |
436 ms |
80544 KB |
Output is correct |
| 6 |
Correct |
446 ms |
80544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
72328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
72464 KB |
Output is correct |
| 3 |
Correct |
0 ms |
72328 KB |
Output is correct |
| 4 |
Correct |
6 ms |
72464 KB |
Output is correct |
| 5 |
Correct |
6 ms |
72464 KB |
Output is correct |
| 6 |
Correct |
3 ms |
72464 KB |
Output is correct |
| 7 |
Correct |
0 ms |
72328 KB |
Output is correct |
| 8 |
Correct |
189 ms |
80152 KB |
Output is correct |
| 9 |
Correct |
253 ms |
75724 KB |
Output is correct |
| 10 |
Correct |
773 ms |
80544 KB |
Output is correct |
| 11 |
Correct |
479 ms |
80544 KB |
Output is correct |
| 12 |
Correct |
436 ms |
80544 KB |
Output is correct |
| 13 |
Correct |
0 ms |
72328 KB |
Output is correct |
| 14 |
Correct |
169 ms |
80152 KB |
Output is correct |
| 15 |
Correct |
43 ms |
72956 KB |
Output is correct |
| 16 |
Correct |
739 ms |
80544 KB |
Output is correct |
| 17 |
Correct |
433 ms |
80544 KB |
Output is correct |
| 18 |
Correct |
433 ms |
80544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
72328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
72464 KB |
Output is correct |
| 3 |
Correct |
0 ms |
72328 KB |
Output is correct |
| 4 |
Correct |
3 ms |
72464 KB |
Output is correct |
| 5 |
Correct |
3 ms |
72464 KB |
Output is correct |
| 6 |
Correct |
3 ms |
72464 KB |
Output is correct |
| 7 |
Correct |
0 ms |
72328 KB |
Output is correct |
| 8 |
Correct |
183 ms |
80152 KB |
Output is correct |
| 9 |
Correct |
276 ms |
75724 KB |
Output is correct |
| 10 |
Correct |
769 ms |
80544 KB |
Output is correct |
| 11 |
Correct |
419 ms |
80544 KB |
Output is correct |
| 12 |
Correct |
486 ms |
80544 KB |
Output is correct |
| 13 |
Correct |
0 ms |
72328 KB |
Output is correct |
| 14 |
Correct |
196 ms |
80152 KB |
Output is correct |
| 15 |
Correct |
39 ms |
72956 KB |
Output is correct |
| 16 |
Correct |
799 ms |
80544 KB |
Output is correct |
| 17 |
Correct |
433 ms |
80544 KB |
Output is correct |
| 18 |
Correct |
453 ms |
80544 KB |
Output is correct |
| 19 |
Correct |
996 ms |
87968 KB |
Output is correct |
| 20 |
Correct |
949 ms |
87968 KB |
Output is correct |
| 21 |
Correct |
906 ms |
87968 KB |
Output is correct |
| 22 |
Correct |
903 ms |
87968 KB |
Output is correct |
| 23 |
Correct |
889 ms |
87968 KB |
Output is correct |
| 24 |
Correct |
926 ms |
87968 KB |
Output is correct |
| 25 |
Correct |
983 ms |
87968 KB |
Output is correct |
| 26 |
Correct |
933 ms |
87968 KB |
Output is correct |
| 27 |
Correct |
1036 ms |
87968 KB |
Output is correct |
| 28 |
Correct |
869 ms |
87968 KB |
Output is correct |
| 29 |
Correct |
1018 ms |
87968 KB |
Output is correct |
| 30 |
Correct |
936 ms |
87968 KB |
Output is correct |
