oj.uz

Submission #139661

# Submission time Handle Problem Language Result Execution time Memory
139661 2019-08-01T08:32:56 Z dcordb Wall (IOI14_wall) C++11
100 / 100
 2123 ms 67920 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
 
const int
	MAX = 2e6 + 5,
	INF = 1e6;
pair <int, int> lazy[4 * MAX];
int a[MAX];

int reduce(const int &a, const int &b, bool &ok) {
	int x = abs(a);
	int y = abs(b);
 
	if(a < 0 && b < 0)
		return (x <= y) ? a : b;
 
	if(a >= 0 && b >= 0)
		return (x <= y) ? b : a;
 
	ok = false;
	return 0;
}
 
void transform(int &a, int &b) {
	int x = abs(a);
	int y = abs(b);
 
	if(a < 0 && b >= 0) {
		if(x <= y) {
			a = INF;
			b *= -1;
		}
 
		else swap(a, b);
	}
 
	else {
		assert(b < 0);
 
		if(x <= y)
			swap(a, b);
 
		else {
			a = -1;
			b *= -1;
		}
	}
}

void reduce(int a, int b) {
	int arr[4] = { lazy[a].first, lazy[a].second, lazy[b].first, lazy[b].second };

	int s[4] = { 0, 0, 0, 0 };
	int k = 0;

	for(int i = 0; i < 4; i++) {
		int o = arr[i];

		if(k == 0) {
			s[k++] = o;
			continue;
		}

		int x = s[k - 1];
		k--;

		bool ok = true;
		int r = reduce(x, o, ok);

		if(ok)
			s[k++] = r;

		else {
			if(k == 0) {
				s[k++] = x;
				s[k++] = o;
			}

			else {
				int y = s[k - 1];
				k--;

				transform(y, x);

				s[k++] = y;

				ok = true;
				r = reduce(x, o, ok);
				assert(ok);

				s[k++] = r;
			}
		}
	}

	lazy[a] = { s[0], s[1] };
}

inline int apply(int x, int y) { return (y >= 0) ? max(x, y) : min(x, -y); }

void build(int x, int st, int nd) {
	lazy[x] = { 0, 0 };
 
	if(st == nd) return;
 
	int mid = (st + nd) >> 1;
	build(2 * x, st, mid);
	build(2 * x + 1, mid + 1, nd);
}
 
void prop(int x, int st, int nd) {
	if(lazy[x] == make_pair(0, 0))
		return;

	if(st == nd) {
		a[st] = apply(a[st], lazy[x].first);
		a[st] = apply(a[st], lazy[x].second);
	}
 
	else {
		reduce(2 * x, x);
		reduce(2 * x + 1, x);
	}
 	
 	lazy[x] = { 0, 0 };
}
 
void upd(int x, int st, int nd, int a, int b, const int &o) {
	prop(x, st, nd);
 
	if(st > b || nd < a)
		return;
 
	if(st >= a && nd <= b) {
		lazy[x] = { o, 0 };
		prop(x, st, nd);
		return;
	}
 
	int mid = (st + nd) >> 1;
	upd(2 * x, st, mid, a, b, o);
	upd(2 * x + 1, mid + 1, nd, a, b, o);
}
 
void buildWall(int n, int m, int operation[], int l[], int r[], int h[], int ans[]) {
	build(1, 0, n - 1);
 
	for(int i = 0; i < m; i++) {
		int height = h[i] + 1;
 
		if(operation[i] == 1)
			upd(1, 0, n - 1, l[i], r[i], height);
 
		else upd(1, 0, n - 1, l[i], r[i], -height);
	}
 
	for(int i = 0; i < n; i++) {
		upd(1, 0, n - 1, i, i, 0);
		ans[i] = max(0, a[i] - 1);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 20 ms 888 KB Output is correct
5 Correct 11 ms 888 KB Output is correct
6 Correct 11 ms 888 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 173 ms 9452 KB Output is correct
3 Correct 521 ms 5368 KB Output is correct
4 Correct 1978 ms 12292 KB Output is correct
5 Correct 374 ms 12536 KB Output is correct
6 Correct 375 ms 12744 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 21 ms 892 KB Output is correct
5 Correct 12 ms 888 KB Output is correct
6 Correct 11 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 177 ms 9500 KB Output is correct
9 Correct 500 ms 5336 KB Output is correct
10 Correct 2123 ms 12264 KB Output is correct
11 Correct 377 ms 12668 KB Output is correct
12 Correct 370 ms 12792 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 176 ms 9156 KB Output is correct
15 Correct 105 ms 2140 KB Output is correct
16 Correct 2076 ms 12364 KB Output is correct
17 Correct 383 ms 12432 KB Output is correct
18 Correct 384 ms 12376 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 20 ms 888 KB Output is correct
5 Correct 11 ms 888 KB Output is correct
6 Correct 12 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 182 ms 9464 KB Output is correct
9 Correct 515 ms 5368 KB Output is correct
10 Correct 2121 ms 12072 KB Output is correct
11 Correct 375 ms 12584 KB Output is correct
12 Correct 379 ms 12780 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 179 ms 9148 KB Output is correct
15 Correct 104 ms 2168 KB Output is correct
16 Correct 2083 ms 12380 KB Output is correct
17 Correct 381 ms 12388 KB Output is correct
18 Correct 379 ms 12368 KB Output is correct
19 Correct 1785 ms 67864 KB Output is correct
20 Correct 1755 ms 65500 KB Output is correct
21 Correct 1747 ms 67920 KB Output is correct
22 Correct 1737 ms 65272 KB Output is correct
23 Correct 1744 ms 65508 KB Output is correct
24 Correct 1785 ms 65272 KB Output is correct
25 Correct 1751 ms 65436 KB Output is correct
26 Correct 1748 ms 67612 KB Output is correct
27 Correct 1746 ms 67704 KB Output is correct
28 Correct 1741 ms 65208 KB Output is correct
29 Correct 1740 ms 65144 KB Output is correct
30 Correct 1757 ms 65048 KB Output is correct