# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
62631 |
2018-07-29T13:52:10 Z |
nvmdava |
Wall (IOI14_wall) |
C++17 |
|
276 ms |
14768 KB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define SIZE 2097155
int maxTree[4 * SIZE], minTree[4 * SIZE], maxLazy[4 * SIZE], minLazy[4 * SIZE];
void down(int id){
if(maxLazy[id] == 0){
if(minLazy[id] == 0){
return;
}
maxTree[id] = min(minLazy[id], maxTree[id]);
minTree[id] = min(minTree[id], maxTree[id]);
minLazy[id << 1] = minLazy[id];
minLazy[id << 1 | 1] = minLazy[id];
minLazy[id] = 0;
} else {
minTree[id] = max(maxLazy[id], minTree[id]);
maxTree[id] = max(minTree[id], maxTree[id]);
maxLazy[id << 1] = maxLazy[id];
maxLazy[id << 1 | 1] = maxLazy[id];
maxLazy[id] = 0;
}
}
void downnn(int id){
if(maxLazy[id] == 0){
if(minLazy[id] == 0){
return;
}
maxTree[id] = min(minLazy[id], maxTree[id]);
minTree[id] = min(minTree[id], maxTree[id]);
} else {
minTree[id] = max(maxLazy[id], minTree[id]);
maxTree[id] = max(minTree[id], maxTree[id]);
}
}
void maximum(int id, int l, int r, int L, int R, int val){
down(id);
if(l == L && r == R){
maxLazy[id] = val;
return;
}
int m = (l + r) >> 1;
if(m >= R){
maximum(id << 1, l, m, L, R, val);
} else if( m < L){
maximum(id << 1 | 1, m + 1, r, L, R ,val);
} else {
maximum(id << 1, l, m, L, m, val);
maximum(id << 1 | 1, m + 1, r, m + 1, R ,val);
}
}
void minimum(int id, int l, int r, int L, int R, int val){
down(id);
if(l == L && r == R){
minLazy[id] = val;
return;
}
int m = (l + r) >> 1;
if(m >= R){
minimum(id << 1, l, m, L, R, val);
} else if( m < L){
minimum(id << 1 | 1, m + 1, r, L, R ,val);
} else {
minimum(id << 1, l, m, L, m, val);
minimum(id << 1 | 1, m + 1, r, m + 1, R ,val);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int i;
for(i = 0; i < k; i++){
if(op[i] == 1) maximum(1, 0, 2097151, left[i], right[i], height[i]);
else minimum(1, 0, 2097151, left[i], right[i], height[i]);
}
for(i = 1; i < 2097152; i++){
down(i);
}
n += 2097152;
for(i = 2097152 ; i < n; i++){
downnn(i);
finalHeight[i - 2097152] = maxTree[i];
}
return;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
376 KB |
Output is correct |
2 |
Correct |
16 ms |
616 KB |
Output is correct |
3 |
Incorrect |
13 ms |
728 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
728 KB |
Output is correct |
2 |
Correct |
276 ms |
14260 KB |
Output is correct |
3 |
Incorrect |
230 ms |
14768 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
14768 KB |
Output is correct |
2 |
Correct |
18 ms |
14768 KB |
Output is correct |
3 |
Incorrect |
17 ms |
14768 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
14768 KB |
Output is correct |
2 |
Correct |
15 ms |
14768 KB |
Output is correct |
3 |
Incorrect |
14 ms |
14768 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |