| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 289559 |
2020-09-02T18:11:18 Z |
cheetose |
Wall (IOI14_wall) |
C++17 |
|
1514 ms |
83556 KB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int mntree[1<<22], mxtree[1<<22], lazy[1<<22];
void propagation(int node, int S, int E)
{
if (lazy[node] != -1)
{
mntree[node] = mxtree[node] = lazy[node];
if (S != E)
{
lazy[2 * node] = lazy[node];
lazy[2 * node + 1] = lazy[node];
}
lazy[node] = -1;
}
}
void upd(int node, int S, int E, int i, int j, int op, int val)
{
propagation(node, S, E);
if (i > E || j < S) return;
if (j >= E && i <= S)
{
if((op==1 && mntree[node]>=val) || (op==2 && mxtree[node]<=val))return;
if((op==1 && mxtree[node]<=val) || (op==2 && mntree[node]>=val)){
lazy[node]=val;
propagation(node,S,E);
return;
}
}
if(S==E)return;
upd(2 * node, S, (S + E) / 2, i, j, op, val);
upd(2 * node + 1, (S + E) / 2 + 1, E, i, j, op, val);
mntree[node] = min(mntree[2 * node], mntree[2 * node + 1]);
mxtree[node] = max(mxtree[2 * node], mxtree[2 * node + 1]);
}
int find(int node,int S,int E,int i,int j){
propagation(node, S, E);
if (i > E || j < S) return -1;
if (j >= E && i <= S) return mxtree[node];
return max(find(node * 2, S, (S + E) / 2, i, j), find(2 * node + 1, (S + E) / 2 + 1, E, i, j));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<k;i++){
int o=op[i],l=left[i],r=right[i],x=height[i];
upd(1,0,n-1,l,r,o,x);
}
for(int i=0;i<n;i++){
finalHeight[i]=find(1,0,n-1,i,i);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
14 ms |
896 KB |
Output is correct |
| 5 |
Correct |
11 ms |
900 KB |
Output is correct |
| 6 |
Correct |
11 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
234 ms |
8184 KB |
Output is correct |
| 3 |
Correct |
215 ms |
4472 KB |
Output is correct |
| 4 |
Correct |
639 ms |
19832 KB |
Output is correct |
| 5 |
Correct |
418 ms |
20124 KB |
Output is correct |
| 6 |
Correct |
398 ms |
20580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
12 ms |
896 KB |
Output is correct |
| 5 |
Correct |
8 ms |
896 KB |
Output is correct |
| 6 |
Correct |
8 ms |
896 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
186 ms |
8132 KB |
Output is correct |
| 9 |
Correct |
209 ms |
4472 KB |
Output is correct |
| 10 |
Correct |
662 ms |
19752 KB |
Output is correct |
| 11 |
Correct |
406 ms |
20088 KB |
Output is correct |
| 12 |
Correct |
405 ms |
20472 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
251 ms |
14072 KB |
Output is correct |
| 15 |
Correct |
47 ms |
2296 KB |
Output is correct |
| 16 |
Correct |
871 ms |
20288 KB |
Output is correct |
| 17 |
Correct |
407 ms |
20344 KB |
Output is correct |
| 18 |
Correct |
406 ms |
20344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
10 ms |
896 KB |
Output is correct |
| 5 |
Correct |
8 ms |
896 KB |
Output is correct |
| 6 |
Correct |
8 ms |
896 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
184 ms |
8184 KB |
Output is correct |
| 9 |
Correct |
211 ms |
4600 KB |
Output is correct |
| 10 |
Correct |
604 ms |
19832 KB |
Output is correct |
| 11 |
Correct |
411 ms |
20344 KB |
Output is correct |
| 12 |
Correct |
387 ms |
20472 KB |
Output is correct |
| 13 |
Correct |
0 ms |
384 KB |
Output is correct |
| 14 |
Correct |
200 ms |
13944 KB |
Output is correct |
| 15 |
Correct |
47 ms |
2304 KB |
Output is correct |
| 16 |
Correct |
896 ms |
20388 KB |
Output is correct |
| 17 |
Correct |
428 ms |
20472 KB |
Output is correct |
| 18 |
Correct |
410 ms |
20472 KB |
Output is correct |
| 19 |
Correct |
1449 ms |
83556 KB |
Output is correct |
| 20 |
Correct |
1478 ms |
78116 KB |
Output is correct |
| 21 |
Correct |
1457 ms |
80684 KB |
Output is correct |
| 22 |
Correct |
1474 ms |
78140 KB |
Output is correct |
| 23 |
Correct |
1514 ms |
78108 KB |
Output is correct |
| 24 |
Correct |
1484 ms |
78088 KB |
Output is correct |
| 25 |
Correct |
1467 ms |
78220 KB |
Output is correct |
| 26 |
Correct |
1450 ms |
80636 KB |
Output is correct |
| 27 |
Correct |
1454 ms |
80764 KB |
Output is correct |
| 28 |
Correct |
1433 ms |
78076 KB |
Output is correct |
| 29 |
Correct |
1450 ms |
78072 KB |
Output is correct |
| 30 |
Correct |
1431 ms |
78088 KB |
Output is correct |
