oj.uz

Submission #164453

# Submission time Handle Problem Language Result Execution time Memory
164453 2019-11-20T17:11:08 Z kostia244 Wall (IOI14_wall) C++17
100 / 100
 2000 ms 130912 KB 
#pragma GCC optimize("Ofast")
#include "wall.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
struct node {
	int mn = 2e9, mx = 0, ord = 1;
	void push(int x, int a) {
		if (a == 1) { //mn
			ord = 1;
			mn = min(mn, x);
			mx = min(mx, mn);
		} else {
			ord = 0;
			mx = max(mx, x);
			mn = max(mn, mx);
		}
	}
	int eval() {
		if (ord == 0) {
			if(mn == 2e9) mn = 0;
			return max(mn, mx);
		}
		return min(mn, mx);
	}
};
node merge(node a, node b) {
	if (b.ord == 1) {
		a.push(b.mx, 0);
		a.push(b.mn, 1);
	} else {
		a.push(b.mn, 1);
		a.push(b.mx, 0);
	}
	return a;
}
node* tree;
void push(int v, int l, int r) {
	if(l==r) return;
	tree[v<<1] = merge(tree[v<<1], tree[v]);
	tree[v<<1|1] = merge(tree[v<<1|1], tree[v]);
	tree[v] = node();
}
int get(int v, int l, int r, int i) {
	push(v, l, r);
	if (l > i || r < i)
		return 0;
	if (l == r)
		return tree[v].eval();
	int mid = (l + r) >> 1;
	return get(v << 1, l, mid, i) + get(v << 1 | 1, mid + 1, r, i);
}
void upd(int v, int l, int r, int ql, int qr, int x, int a) {
	push(v, l, r);
	if (r < ql || l > qr)
		return;
	if (ql <= l && r <= qr) {
//		cout << l << " " << r << " " << tree[v].eval() << "\n";
		tree[v].push(x, a);
//		cout << l << " " << r << " " << x << " " << a << " " << tree[v].ord << "\n";
		push(v, l, r);
		return;
	}
	int mid = (l + r) >> 1;
	upd(v << 1, l, mid, ql, qr, x, a);
	upd(v << 1 | 1, mid + 1, r, ql, qr, x, a);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[]) {
	tree = new node[4*n + 10];
	for(int i = 0; i < k; i++) {
		upd(1, 0, n-1, l[i], r[i], h[i], (op[i]-1));
//		cout <<"======\n";
	}
	for(int i = 0; i < n; i++)
		fh[i] = get(1, 0, n-1, i);
	return;
}

Subtask #1
8.0 / 8.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 12 ms 1016 KB Output is correct
5 Correct 11 ms 1016 KB Output is correct
6 Correct 11 ms 1016 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 178 ms 8992 KB Output is correct
3 Correct 251 ms 5496 KB Output is correct
4 Correct 752 ms 14344 KB Output is correct
5 Correct 440 ms 15028 KB Output is correct
6 Correct 430 ms 14840 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 12 ms 1016 KB Output is correct
5 Correct 11 ms 1016 KB Output is correct
6 Correct 11 ms 1144 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 178 ms 9080 KB Output is correct
9 Correct 248 ms 5496 KB Output is correct
10 Correct 764 ms 14328 KB Output is correct
11 Correct 496 ms 14924 KB Output is correct
12 Correct 477 ms 14844 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 183 ms 9108 KB Output is correct
15 Correct 46 ms 2296 KB Output is correct
16 Correct 767 ms 14580 KB Output is correct
17 Correct 456 ms 14584 KB Output is correct
18 Correct 470 ms 14712 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 12 ms 1144 KB Output is correct
5 Correct 11 ms 1016 KB Output is correct
6 Correct 11 ms 1016 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 178 ms 9080 KB Output is correct
9 Correct 255 ms 5468 KB Output is correct
10 Correct 778 ms 14452 KB Output is correct
11 Correct 449 ms 14964 KB Output is correct
12 Correct 438 ms 14888 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 181 ms 9080 KB Output is correct
15 Correct 46 ms 2296 KB Output is correct
16 Correct 776 ms 14584 KB Output is correct
17 Correct 436 ms 14448 KB Output is correct
18 Correct 437 ms 14448 KB Output is correct
19 Correct 1873 ms 120644 KB Output is correct
20 Correct 1855 ms 128256 KB Output is correct
21 Correct 2000 ms 130720 KB Output is correct
22 Correct 1850 ms 128212 KB Output is correct
23 Correct 1873 ms 128128 KB Output is correct
24 Correct 1864 ms 128148 KB Output is correct
25 Correct 1877 ms 128220 KB Output is correct
26 Correct 1854 ms 130748 KB Output is correct
27 Correct 1918 ms 130912 KB Output is correct
28 Correct 1855 ms 128232 KB Output is correct
29 Correct 1842 ms 128248 KB Output is correct
30 Correct 1848 ms 128248 KB Output is correct