oj.uz

Submission #351257

# Submission time Handle Problem Language Result Execution time Memory
351257 2021-01-19T17:39:07 Z NachoLibre Wall (IOI14_wall) C++14
100 / 100
 1490 ms 140236 KB 
#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "wall.h"
#endif

const int R = 100000;

struct vyv {
	vyv *l, *r;
	int xl, xr;
	vyv() {
		l = r = NULL;
		xl = 0;
		xr = R;
	}

	void P() {
		if(l == NULL) l = new vyv();
		if(r == NULL) r = new vyv();
		xl = max(l->xl, r->xl);
		xr = min(l->xr, r->xr);
		if(xl > xr) {
			if(l->xl > r->xr) {
				xl = xr = r->xr;
			} else if(l->xr < r->xl) {
				xl = xr = r->xl;
			} else {
				exit(1);
			}
		}
	}
} *rt = new vyv();

int globk;
void gnk(int si, int vl, int vr, int l = 0, int r = globk - 1, vyv *&t = rt) {
	if(t == NULL) t = new vyv();
	if(l == r) {
		t->xl = vl;
		t->xr = vr;
		return;
	}
	int m = (l + r) / 2;
	if(m >= si) gnk(si, vl, vr, l, m, t->l);
	else gnk(si, vl, vr, m + 1, r, t->r);
	t->P();
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int dr[]) {
	globk = k;
	vector<pair<int, pair<int, int>>> v[n + 1];
	for(int i = 0; i < k; ++i) {
		int xl = 0, xr = R;
		if(op[i] == 1) xl = h[i];
		else xr = h[i];
		v[l[i]].push_back({i, {xl, xr}});
		v[r[i] + 1].push_back({i, {0, R}});
	}
	for(int i = 0; i < n; ++i) {
		for(auto p : v[i]) {
			gnk(p.first, p.second.first, p.second.second);
		}
		dr[i] = rt->xl;
	}
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}
#endif

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 4 ms 876 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 7 ms 1260 KB Output is correct
5 Correct 6 ms 1260 KB Output is correct
6 Correct 8 ms 1388 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 319 ms 51252 KB Output is correct
3 Correct 385 ms 24172 KB Output is correct
4 Correct 1442 ms 60396 KB Output is correct
5 Correct 470 ms 59116 KB Output is correct
6 Correct 486 ms 67596 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 4 ms 876 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 8 ms 1260 KB Output is correct
5 Correct 6 ms 1260 KB Output is correct
6 Correct 7 ms 1388 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 322 ms 57012 KB Output is correct
9 Correct 398 ms 28068 KB Output is correct
10 Correct 1363 ms 70124 KB Output is correct
11 Correct 488 ms 69228 KB Output is correct
12 Correct 470 ms 67564 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 349 ms 57140 KB Output is correct
15 Correct 46 ms 4972 KB Output is correct
16 Correct 1490 ms 70316 KB Output is correct
17 Correct 545 ms 67564 KB Output is correct
18 Correct 542 ms 67348 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 3 ms 876 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 7 ms 1260 KB Output is correct
5 Correct 6 ms 1260 KB Output is correct
6 Correct 6 ms 1388 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 325 ms 57140 KB Output is correct
9 Correct 390 ms 28012 KB Output is correct
10 Correct 1409 ms 70124 KB Output is correct
11 Correct 479 ms 69228 KB Output is correct
12 Correct 472 ms 67564 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 349 ms 57012 KB Output is correct
15 Correct 44 ms 4972 KB Output is correct
16 Correct 1481 ms 70124 KB Output is correct
17 Correct 521 ms 67436 KB Output is correct
18 Correct 523 ms 67436 KB Output is correct
19 Correct 817 ms 140012 KB Output is correct
20 Correct 809 ms 137688 KB Output is correct
21 Correct 826 ms 140236 KB Output is correct
22 Correct 811 ms 137836 KB Output is correct
23 Correct 812 ms 137528 KB Output is correct
24 Correct 827 ms 137688 KB Output is correct
25 Correct 816 ms 137608 KB Output is correct
26 Correct 854 ms 140024 KB Output is correct
27 Correct 822 ms 140124 KB Output is correct
28 Correct 816 ms 137580 KB Output is correct
29 Correct 810 ms 137580 KB Output is correct
30 Correct 809 ms 137580 KB Output is correct