oj.uz

Submission #485436

# Submission time Handle Problem Language Result Execution time Memory
485436 2021-11-07T18:35:12 Z penguinhacker Wall (IOI14_wall) C++14
100 / 100
 621 ms 69732 KB 
#include <bits/stdc++.h>
#include <wall.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e6;
const ar<int, 2> ID={0, mxN};
int n;
ar<int, 2> st[1<<22];

ar<int, 2> app(ar<int, 2> a, ar<int, 2> b) {
	a[0]=max(a[0], b[0]);
	a[1]=max(a[1], b[0]);
	a[0]=min(a[0], b[1]);
	a[1]=min(a[1], b[1]);
	return a;
}

void psh(int u) {
	if (st[u]!=ID) {
		st[2*u]=app(st[2*u], st[u]);
		st[2*u+1]=app(st[2*u+1], st[u]);
		st[u]=ID;
	}
}

void upd(int ql, int qr, ar<int, 2> x, int u=1, int l=0, int r=n-1) {
	if (ql<=l&&r<=qr) {
		st[u]=app(st[u], x);
		return;
	}
	psh(u);
	int mid=(l+r)/2;
	if (ql<=mid)
		upd(ql, qr, x, 2*u, l, mid);
	if (qr>mid)
		upd(ql, qr, x, 2*u+1, mid+1, r);
}

void solve(int ans[], int u=1, int l=0, int r=n-1) {
	if (l==r) {
		assert(st[u][0]==st[u][1]);
		ans[l]=st[u][0];
		return;
	}
	int mid=(l+r)/2;
	psh(u);
	solve(ans, 2*u, l, mid);
	solve(ans, 2*u+1, mid+1, r);
}

void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	n=_n;
	for (int i=0; i<k; ++i) {
		if (op[i]==1)
			upd(left[i], right[i], {height[i], mxN});
		else
			upd(left[i], right[i], {0, height[i]});
	}
	solve(finalHeight);
}

/*int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _n=10, _k=6;
	int _op[6]={1, 2, 2, 1, 1, 2};
	int _left[6]={1, 4, 3, 0, 2, 6};
	int _right[6]={8, 9, 6, 5, 2, 7};
	int _height[6]={4, 1, 5, 3, 5, 0};
	int _ans[10];
	buildWall(_n, _k, _op, _left, _right, _height, _ans);
	for (int i=0; i<10; ++i)
		cout << _ans[i] << " ";
	return 0;
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 716 KB Output is correct
5 Correct 4 ms 692 KB Output is correct
6 Correct 4 ms 716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 131 ms 8348 KB Output is correct
3 Correct 169 ms 4388 KB Output is correct
4 Correct 468 ms 20300 KB Output is correct
5 Correct 261 ms 21444 KB Output is correct
6 Correct 238 ms 19748 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 5 ms 716 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 138 ms 13888 KB Output is correct
9 Correct 165 ms 7932 KB Output is correct
10 Correct 448 ms 20324 KB Output is correct
11 Correct 258 ms 21388 KB Output is correct
12 Correct 235 ms 19760 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 139 ms 13852 KB Output is correct
15 Correct 28 ms 1984 KB Output is correct
16 Correct 454 ms 20620 KB Output is correct
17 Correct 246 ms 20036 KB Output is correct
18 Correct 256 ms 20032 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 716 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 132 ms 13920 KB Output is correct
9 Correct 173 ms 7904 KB Output is correct
10 Correct 452 ms 20320 KB Output is correct
11 Correct 254 ms 21384 KB Output is correct
12 Correct 244 ms 19780 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 136 ms 13932 KB Output is correct
15 Correct 27 ms 1996 KB Output is correct
16 Correct 461 ms 20556 KB Output is correct
17 Correct 242 ms 19980 KB Output is correct
18 Correct 244 ms 20112 KB Output is correct
19 Correct 596 ms 69428 KB Output is correct
20 Correct 603 ms 66996 KB Output is correct
21 Correct 616 ms 69732 KB Output is correct
22 Correct 607 ms 67376 KB Output is correct
23 Correct 607 ms 66952 KB Output is correct
24 Correct 613 ms 66912 KB Output is correct
25 Correct 600 ms 66936 KB Output is correct
26 Correct 621 ms 69704 KB Output is correct
27 Correct 607 ms 69672 KB Output is correct
28 Correct 600 ms 67076 KB Output is correct
29 Correct 598 ms 66980 KB Output is correct
30 Correct 601 ms 66884 KB Output is correct