oj.uz

Submission #155890

# Submission time Handle Problem Language Result Execution time Memory
155890 2019-10-01T16:18:45 Z jhnah917 Wall (IOI14_wall) C++14
100 / 100
 1405 ms 102460 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p; //lower bound, upper bound

int *ans;
p tree[1 << 22];

void push(int node, int op, ll v){
	if(op == 1){
		tree[node].x = max(tree[node].x, v);
		tree[node].y = max(tree[node].y, v);
	}else{
		tree[node].x = min(tree[node].x, v);
		tree[node].y = min(tree[node].y, v);
	}
}

void update(int node, int s, int e, int l, int r, int op, ll v){
	if(r < s || e < l) return;
	if(l <= s && e <= r){
		push(node, op, v);
		ans[l] = tree[node].x;
		return;
	}
	int m = s + e >> 1;
	push(node*2, 1, tree[node].x);
	push(node*2, 2, tree[node].y);
	push(node*2+1, 1, tree[node].x);
	push(node*2+1, 2, tree[node].y);
	tree[node].x = 0, tree[node].y = 1e9;
	update(node*2, s, m, l, r, op, v);
	update(node*2+1, m+1, e, l, r, op, v);
}

void buildWall(int n, int k, int op[], int lf[], int rf[], int h[], int res[]){
	ans = res;
	for(int i=0; i<k; i++){
		update(1, 0, n-1, lf[i], rf[i], op[i], h[i]);
	}
	for(int i=0; i<n; i++){
		update(1, 0, n-1, i, i, 1, 0);
	}
}

Compilation message

wall.cpp: In function 'void update(int, int, int, int, int, int, ll)':
wall.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s + e >> 1;
          ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 508 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 10 ms 1144 KB Output is correct
5 Correct 10 ms 1144 KB Output is correct
6 Correct 9 ms 1144 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 180 ms 14088 KB Output is correct
3 Correct 210 ms 8540 KB Output is correct
4 Correct 631 ms 22452 KB Output is correct
5 Correct 368 ms 23544 KB Output is correct
6 Correct 364 ms 22132 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 10 ms 1144 KB Output is correct
5 Correct 10 ms 1016 KB Output is correct
6 Correct 7 ms 1144 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 184 ms 14056 KB Output is correct
9 Correct 220 ms 8516 KB Output is correct
10 Correct 637 ms 22456 KB Output is correct
11 Correct 368 ms 23480 KB Output is correct
12 Correct 366 ms 22012 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 188 ms 13992 KB Output is correct
15 Correct 40 ms 2504 KB Output is correct
16 Correct 618 ms 22740 KB Output is correct
17 Correct 361 ms 22188 KB Output is correct
18 Correct 371 ms 22140 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 10 ms 1148 KB Output is correct
5 Correct 9 ms 1144 KB Output is correct
6 Correct 9 ms 1144 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 179 ms 14020 KB Output is correct
9 Correct 210 ms 8568 KB Output is correct
10 Correct 670 ms 22588 KB Output is correct
11 Correct 366 ms 23548 KB Output is correct
12 Correct 360 ms 22044 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 183 ms 14040 KB Output is correct
15 Correct 39 ms 2552 KB Output is correct
16 Correct 687 ms 22780 KB Output is correct
17 Correct 370 ms 22184 KB Output is correct
18 Correct 374 ms 22192 KB Output is correct
19 Correct 1396 ms 102436 KB Output is correct
20 Correct 1405 ms 99892 KB Output is correct
21 Correct 1398 ms 102448 KB Output is correct
22 Correct 1402 ms 99988 KB Output is correct
23 Correct 1383 ms 99832 KB Output is correct
24 Correct 1396 ms 99840 KB Output is correct
25 Correct 1387 ms 99988 KB Output is correct
26 Correct 1396 ms 102460 KB Output is correct
27 Correct 1394 ms 102352 KB Output is correct
28 Correct 1393 ms 99992 KB Output is correct
29 Correct 1399 ms 100012 KB Output is correct
30 Correct 1391 ms 99840 KB Output is correct