oj.uz

Submission #106668

# Submission time Handle Problem Language Result Execution time Memory
106668 2019-04-19T14:28:24 Z tincamatei Wall (IOI14_wall) C++14
100 / 100
 1453 ms 127140 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000000;
const int MAX_K = 500000;
const int MAX_VAL = 100000;

struct Range {
	int l, r;

	Range():l(0), r(MAX_VAL + 1) {}
	Range(int _l, int _r):l(_l), r(_r) {}

	Range operator+ (const Range &x) const {
		return Range(max(l, x.l), min(r, x.r));
	}
};

Range aint[1+4*MAX_K];

void update(int poz, Range x, int l = 0, int r = MAX_K - 1, int nod = 1) {
	if(poz < l || r < poz) return;

	if(l == r)
		aint[nod] = x;
	else {
		int mid = (l + r) / 2;
		update(poz, x, l, mid, 2 * nod);
		update(poz, x, mid + 1, r, 2 * nod + 1);
		aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
	}
}

bool intersect(const Range &x) {
	return x.l > x.r;
}

int query(Range &x, int l = 0, int r = MAX_K - 1, int nod = 1) {
	if(l == r)
		return l;
	else {
		int mid = (l + r) / 2;
		if(intersect(x + aint[2 * nod + 1]))
			return query(x, mid + 1, r, 2 * nod + 1);
		else {
			x = x + aint[2 * nod + 1];
			return query(x, l, mid, 2 * nod);
		}
	}
}

struct Event {
	Range x;
	int poz;
};

vector<Event> evs[MAX_N + 1];
Range mod[MAX_K];

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = 0; i < k; ++i) {
		if(op[i] == 1)
			evs[left[i]].push_back({Range(height[i], MAX_VAL + 1), i});
		else
			evs[left[i]].push_back({Range(0, height[i]), i});
		evs[right[i] + 1].push_back({Range(), i});
	}

	int rez = 0;

	for(int i = 0; i < n; ++i) {
		for(auto it: evs[i]) {
			update(it.poz, it.x);
			mod[it.poz] = it.x;
		}
		
		if(!evs[i].empty()) {
			Range last = Range();
			int poz;
	
			poz = query(last);
	
			if((last + mod[poz]).l <= last.r)
				rez = (last + mod[poz]).l;
			else if((last + mod[poz]).l > last.r)
				rez = last.r;
			else
				rez = last.l;
		}

		finalHeight[i] = rez;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 66808 KB Output is correct
2 Correct 64 ms 67196 KB Output is correct
3 Correct 63 ms 67064 KB Output is correct
4 Correct 70 ms 67320 KB Output is correct
5 Correct 72 ms 67320 KB Output is correct
6 Correct 62 ms 67392 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 66808 KB Output is correct
2 Correct 400 ms 92608 KB Output is correct
3 Correct 389 ms 81756 KB Output is correct
4 Correct 1237 ms 104792 KB Output is correct
5 Correct 459 ms 102740 KB Output is correct
6 Correct 519 ms 100820 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 66872 KB Output is correct
2 Correct 79 ms 67272 KB Output is correct
3 Correct 68 ms 66940 KB Output is correct
4 Correct 85 ms 67388 KB Output is correct
5 Correct 87 ms 67440 KB Output is correct
6 Correct 78 ms 67448 KB Output is correct
7 Correct 71 ms 66808 KB Output is correct
8 Correct 346 ms 92544 KB Output is correct
9 Correct 387 ms 81840 KB Output is correct
10 Correct 1453 ms 104800 KB Output is correct
11 Correct 641 ms 102248 KB Output is correct
12 Correct 490 ms 101016 KB Output is correct
13 Correct 56 ms 66808 KB Output is correct
14 Correct 303 ms 92564 KB Output is correct
15 Correct 100 ms 69368 KB Output is correct
16 Correct 1162 ms 105024 KB Output is correct
17 Correct 560 ms 100948 KB Output is correct
18 Correct 586 ms 100348 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 66808 KB Output is correct
2 Correct 69 ms 67228 KB Output is correct
3 Correct 76 ms 66936 KB Output is correct
4 Correct 73 ms 67420 KB Output is correct
5 Correct 62 ms 67320 KB Output is correct
6 Correct 75 ms 67320 KB Output is correct
7 Correct 65 ms 66808 KB Output is correct
8 Correct 354 ms 92520 KB Output is correct
9 Correct 454 ms 81712 KB Output is correct
10 Correct 1252 ms 104752 KB Output is correct
11 Correct 553 ms 102364 KB Output is correct
12 Correct 481 ms 100828 KB Output is correct
13 Correct 56 ms 66904 KB Output is correct
14 Correct 309 ms 92644 KB Output is correct
15 Correct 102 ms 69356 KB Output is correct
16 Correct 1344 ms 105036 KB Output is correct
17 Correct 606 ms 100884 KB Output is correct
18 Correct 597 ms 100208 KB Output is correct
19 Correct 1032 ms 127084 KB Output is correct
20 Correct 885 ms 124664 KB Output is correct
21 Correct 807 ms 127068 KB Output is correct
22 Correct 754 ms 124784 KB Output is correct
23 Correct 928 ms 124560 KB Output is correct
24 Correct 876 ms 124472 KB Output is correct
25 Correct 855 ms 124456 KB Output is correct
26 Correct 922 ms 126948 KB Output is correct
27 Correct 860 ms 127140 KB Output is correct
28 Correct 763 ms 124720 KB Output is correct
29 Correct 733 ms 124652 KB Output is correct
30 Correct 750 ms 124568 KB Output is correct