oj.uz

Submission #106473

# Submission time Handle Problem Language Result Execution time Memory
106473 2019-04-18T17:10:35 Z tincamatei Wall (IOI14_wall) C++14
100 / 100
 1182 ms 128244 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});
	}

	for(int i = 0; i < n; ++i) {
		for(auto it: evs[i]) {
			update(it.poz, it.x);
			mod[it.poz] = it.x;
		}
		
		Range last = Range();
		int poz;

		poz = query(last);

		if((last + mod[poz]).l <= last.r)
			finalHeight[i] = (last + mod[poz]).l;
		else if((last + mod[poz]).l > last.r)
			finalHeight[i] = last.r;
		else
			finalHeight[i] = last.l;
	}
}

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 67240 KB Output is correct
3 Correct 57 ms 67064 KB Output is correct
4 Correct 67 ms 67320 KB Output is correct
5 Correct 67 ms 67448 KB Output is correct
6 Correct 61 ms 67320 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 66860 KB Output is correct
2 Correct 308 ms 92728 KB Output is correct
3 Correct 396 ms 81904 KB Output is correct
4 Correct 1114 ms 104760 KB Output is correct
5 Correct 456 ms 103032 KB Output is correct
6 Correct 507 ms 100804 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 66880 KB Output is correct
2 Correct 59 ms 67192 KB Output is correct
3 Correct 61 ms 66936 KB Output is correct
4 Correct 63 ms 67320 KB Output is correct
5 Correct 62 ms 67448 KB Output is correct
6 Correct 71 ms 67320 KB Output is correct
7 Correct 60 ms 66808 KB Output is correct
8 Correct 354 ms 92720 KB Output is correct
9 Correct 381 ms 81760 KB Output is correct
10 Correct 1155 ms 105068 KB Output is correct
11 Correct 565 ms 102904 KB Output is correct
12 Correct 517 ms 100868 KB Output is correct
13 Correct 73 ms 66808 KB Output is correct
14 Correct 359 ms 92612 KB Output is correct
15 Correct 98 ms 69368 KB Output is correct
16 Correct 1182 ms 105164 KB Output is correct
17 Correct 535 ms 100844 KB Output is correct
18 Correct 557 ms 100216 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 66988 KB Output is correct
2 Correct 64 ms 67240 KB Output is correct
3 Correct 63 ms 66936 KB Output is correct
4 Correct 73 ms 67320 KB Output is correct
5 Correct 77 ms 67320 KB Output is correct
6 Correct 64 ms 67332 KB Output is correct
7 Correct 55 ms 66812 KB Output is correct
8 Correct 318 ms 92692 KB Output is correct
9 Correct 356 ms 81784 KB Output is correct
10 Correct 1142 ms 104908 KB Output is correct
11 Correct 497 ms 102904 KB Output is correct
12 Correct 500 ms 100856 KB Output is correct
13 Correct 66 ms 66936 KB Output is correct
14 Correct 382 ms 92672 KB Output is correct
15 Correct 111 ms 69368 KB Output is correct
16 Correct 1050 ms 105088 KB Output is correct
17 Correct 506 ms 100800 KB Output is correct
18 Correct 486 ms 100384 KB Output is correct
19 Correct 1027 ms 128244 KB Output is correct
20 Correct 777 ms 125840 KB Output is correct
21 Correct 758 ms 128180 KB Output is correct
22 Correct 784 ms 125784 KB Output is correct
23 Correct 745 ms 125740 KB Output is correct
24 Correct 819 ms 125760 KB Output is correct
25 Correct 803 ms 125816 KB Output is correct
26 Correct 916 ms 128164 KB Output is correct
27 Correct 886 ms 128120 KB Output is correct
28 Correct 837 ms 125736 KB Output is correct
29 Correct 749 ms 125688 KB Output is correct
30 Correct 767 ms 125944 KB Output is correct