| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 7529 |
2014-08-10T12:33:22 Z |
qja0950 |
Wall (IOI14_wall) |
C++ |
|
2340 ms |
141720 KB |
#include "wall.h"
#include <stdio.h>
#define INF 2100000000
struct NODE{
int min, max;
NODE *left, *right;
NODE(int a, int b) {
NODE::min = a;
NODE::max = b;
NODE::left = NULL;
NODE::right= NULL;
}
};
void Upload(NODE *node, int op, int h) {
if(op == 1) {
if(node->min < h) node->min = h;
if(node->max < h) node->max = h;
}
if(op == 2) {
if(node->min > h) node->min = h;
if(node->max > h) node->max = h;
}
return;
}
int *Final;
void Change(NODE *now, int a, int b, int x, int y, int op, int h) {
if(b<x || y<a) return;
if(x<=a && b<=y) {
Final[a] = now->min;
Upload(now, op, h);
return;
}
if(now->left == NULL) {
now->left = new NODE(0, INF);
now->right= new NODE(0, INF);
}
Upload(now->left , 1, now->min);
Upload(now->left , 2, now->max);
Upload(now->right, 1, now->min);
Upload(now->right, 2, now->max);
now->min = 0;
now->max = INF;
int m = (a+b)/2;
Change(now->left , a , m, x, y, op, h);
Change(now->right , m+1 , b, x, y, op, h);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
NODE *root = new NODE(0, 0);
Final = finalHeight;
for(int i=0; i<k; i++)
Change(root, 0, n-1, left[i], right[i], op[i], height[i]);
for(int i=0; i<n; i++)
Change(root, 0, n-1, i, i, 2, INF);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 4 |
Correct |
12 ms |
1868 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1868 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 2 |
Correct |
172 ms |
9032 KB |
Output is correct |
| 3 |
Correct |
284 ms |
5644 KB |
Output is correct |
| 4 |
Correct |
984 ms |
15628 KB |
Output is correct |
| 5 |
Correct |
524 ms |
15628 KB |
Output is correct |
| 6 |
Correct |
524 ms |
15628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 4 |
Correct |
12 ms |
1868 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1868 KB |
Output is correct |
| 6 |
Correct |
12 ms |
1868 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 8 |
Correct |
168 ms |
9032 KB |
Output is correct |
| 9 |
Correct |
292 ms |
5644 KB |
Output is correct |
| 10 |
Correct |
924 ms |
15628 KB |
Output is correct |
| 11 |
Correct |
524 ms |
15628 KB |
Output is correct |
| 12 |
Correct |
484 ms |
15628 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 14 |
Correct |
196 ms |
9032 KB |
Output is correct |
| 15 |
Correct |
60 ms |
2748 KB |
Output is correct |
| 16 |
Correct |
992 ms |
15628 KB |
Output is correct |
| 17 |
Correct |
532 ms |
15628 KB |
Output is correct |
| 18 |
Correct |
516 ms |
15628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1868 KB |
Output is correct |
| 5 |
Correct |
8 ms |
1868 KB |
Output is correct |
| 6 |
Correct |
12 ms |
1868 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 8 |
Correct |
176 ms |
9032 KB |
Output is correct |
| 9 |
Correct |
304 ms |
5644 KB |
Output is correct |
| 10 |
Correct |
944 ms |
15628 KB |
Output is correct |
| 11 |
Correct |
536 ms |
15628 KB |
Output is correct |
| 12 |
Correct |
516 ms |
15628 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 14 |
Correct |
180 ms |
9032 KB |
Output is correct |
| 15 |
Correct |
52 ms |
2748 KB |
Output is correct |
| 16 |
Correct |
1008 ms |
15628 KB |
Output is correct |
| 17 |
Correct |
520 ms |
15628 KB |
Output is correct |
| 18 |
Correct |
524 ms |
15628 KB |
Output is correct |
| 19 |
Correct |
2324 ms |
141720 KB |
Output is correct |
| 20 |
Correct |
2268 ms |
141720 KB |
Output is correct |
| 21 |
Correct |
2324 ms |
141720 KB |
Output is correct |
| 22 |
Correct |
2332 ms |
141720 KB |
Output is correct |
| 23 |
Correct |
2340 ms |
141720 KB |
Output is correct |
| 24 |
Correct |
2260 ms |
141720 KB |
Output is correct |
| 25 |
Correct |
2304 ms |
141720 KB |
Output is correct |
| 26 |
Correct |
2304 ms |
141720 KB |
Output is correct |
| 27 |
Correct |
2324 ms |
141720 KB |
Output is correct |
| 28 |
Correct |
2308 ms |
141720 KB |
Output is correct |
| 29 |
Correct |
2280 ms |
141720 KB |
Output is correct |
| 30 |
Correct |
2292 ms |
141720 KB |
Output is correct |
