oj.uz

Submission #130504

# Submission time Handle Problem Language Result Execution time Memory
130504 2019-07-15T11:20:28 Z antimirage Wall (IOI14_wall) C++14
100 / 100
 1108 ms 99528 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 5;	

int mx[N * 4], mn[N * 4], n;

void upd (int v, int val, int t) {
	if (t == 1) {
		mn[v] = max(mn[v], val);
		mx[v] = max(mx[v], val);
	}
	else {
		mn[v] = min(mn[v], val);
		mx[v] = min(mx[v], val);
	}
}
void push (int v) {
	upd(v + v, mx[v], 1);
	upd(v + v, mn[v], 2);
	upd(v + v + 1, mx[v], 1);
	upd(v + v + 1, mn[v], 2);
	mx[v] = 0;
	mn[v] = 1e9;
}
void update (int l, int r, int val, int t, int v = 1, int tl = 1, int tr = n) {
	if (l > tr || tl > r)
		return;
		
	if (l <= tl && tr <= r) {
		upd(v, val, t);
		return;
	}
	push(v);
	int tm = (tl + tr) >> 1;
	update(l, r, val, t, v + v, tl, tm);
	update(l, r, val, t, v + v + 1, tm + 1, tr);
}
int get (int pos, int v = 1, int tl = 1, int tr = n) {
	if (tl == tr)
		return mx[v];
	push(v);	
	int tm = (tl + tr) >> 1;
	
	if (pos <= tm)
		return get(pos, v + v, tl, tm);
	return get(pos, v + v + 1, tm + 1, tr);
}
void buildWall(int N, int k, int op[], int l[], int r[], int a[], int ans[]) { 
	n = N;
	
	memset(mn, 0x3f3f3f3f, sizeof(mn));
	memset(mx, 0, sizeof(mx));
	for (int i = 0; i < k; i++) {
		update( l[i] + 1, r[i] + 1, a[i], op[i] );		
	}
	for (int i = 0; i < n; i++) {
		ans[i] = get(i + 1);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 63096 KB Output is correct
2 Correct 57 ms 63208 KB Output is correct
3 Correct 55 ms 62968 KB Output is correct
4 Correct 61 ms 63224 KB Output is correct
5 Correct 60 ms 63196 KB Output is correct
6 Correct 61 ms 63224 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 63136 KB Output is correct
2 Correct 226 ms 76788 KB Output is correct
3 Correct 256 ms 70072 KB Output is correct
4 Correct 632 ms 80964 KB Output is correct
5 Correct 405 ms 82024 KB Output is correct
6 Correct 394 ms 80504 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 63096 KB Output is correct
2 Correct 56 ms 63100 KB Output is correct
3 Correct 55 ms 62968 KB Output is correct
4 Correct 62 ms 63224 KB Output is correct
5 Correct 61 ms 63228 KB Output is correct
6 Correct 62 ms 63224 KB Output is correct
7 Correct 54 ms 62968 KB Output is correct
8 Correct 227 ms 76664 KB Output is correct
9 Correct 256 ms 70136 KB Output is correct
10 Correct 636 ms 81020 KB Output is correct
11 Correct 405 ms 82084 KB Output is correct
12 Correct 396 ms 80476 KB Output is correct
13 Correct 55 ms 62968 KB Output is correct
14 Correct 229 ms 76700 KB Output is correct
15 Correct 90 ms 64380 KB Output is correct
16 Correct 627 ms 81192 KB Output is correct
17 Correct 398 ms 80604 KB Output is correct
18 Correct 398 ms 80624 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 63136 KB Output is correct
2 Correct 54 ms 63016 KB Output is correct
3 Correct 61 ms 63096 KB Output is correct
4 Correct 62 ms 63200 KB Output is correct
5 Correct 59 ms 63160 KB Output is correct
6 Correct 71 ms 63204 KB Output is correct
7 Correct 63 ms 62908 KB Output is correct
8 Correct 236 ms 76628 KB Output is correct
9 Correct 253 ms 70236 KB Output is correct
10 Correct 635 ms 80972 KB Output is correct
11 Correct 403 ms 82040 KB Output is correct
12 Correct 391 ms 80504 KB Output is correct
13 Correct 53 ms 62968 KB Output is correct
14 Correct 224 ms 76604 KB Output is correct
15 Correct 86 ms 64248 KB Output is correct
16 Correct 629 ms 81440 KB Output is correct
17 Correct 396 ms 80760 KB Output is correct
18 Correct 398 ms 80760 KB Output is correct
19 Correct 1094 ms 99316 KB Output is correct
20 Correct 1088 ms 96784 KB Output is correct
21 Correct 1100 ms 99404 KB Output is correct
22 Correct 1099 ms 96824 KB Output is correct
23 Correct 1094 ms 96904 KB Output is correct
24 Correct 1079 ms 96864 KB Output is correct
25 Correct 1105 ms 96796 KB Output is correct
26 Correct 1103 ms 99296 KB Output is correct
27 Correct 1108 ms 99528 KB Output is correct
28 Correct 1082 ms 96980 KB Output is correct
29 Correct 1079 ms 97012 KB Output is correct
30 Correct 1087 ms 96868 KB Output is correct