oj.uz

Submission #140011

# Submission time Handle Problem Language Result Execution time Memory
140011 2019-08-01T20:38:06 Z dcordb Wall (IOI14_wall) C++11
100 / 100
 1585 ms 68460 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;
		}
	}
}

pair <int, int> reduce(pair <int, int> a, pair <int, int> b) {
	transform(a.second, b.first);

	bool ok = true;
	int r1 = reduce(a.first, a.second, ok);

	ok = true;
	int r2 = reduce(b.first, b.second, ok);

	ok = true;
	int r = reduce(r1, r2, ok);

	if(ok) {
		if(r < 0)
			return { r, 0 };
		return { -INF, r };
	}

	if(r1 >= 0)
		transform(r1, r2);

	return { r1, r2 };
}

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] = { -INF, 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(-INF, 0))
		return;

	if(st == nd) {
		a[st] = apply(a[st], lazy[x].first);
		a[st] = apply(a[st], lazy[x].second);
	}
 
	else {
		lazy[2 * x] = reduce(lazy[2 * x], lazy[x]);
		lazy[2 * x + 1] = reduce(lazy[2 * x + 1], lazy[x]);
	}
 	
 	lazy[x] = { -INF, 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) {
		if(o < 0)
			lazy[x] = { o, 0 };

		else lazy[x] = { -INF, o };

		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, 1);
		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 508 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 16 ms 888 KB Output is correct
5 Correct 10 ms 888 KB Output is correct
6 Correct 10 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 174 ms 9640 KB Output is correct
3 Correct 452 ms 5752 KB Output is correct
4 Correct 1397 ms 12472 KB Output is correct
5 Correct 369 ms 13152 KB Output is correct
6 Correct 360 ms 12920 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 4 ms 376 KB Output is correct
4 Correct 16 ms 924 KB Output is correct
5 Correct 10 ms 888 KB Output is correct
6 Correct 10 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 173 ms 9628 KB Output is correct
9 Correct 445 ms 5752 KB Output is correct
10 Correct 1399 ms 12512 KB Output is correct
11 Correct 382 ms 13072 KB Output is correct
12 Correct 370 ms 13176 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 176 ms 9592 KB Output is correct
15 Correct 82 ms 2168 KB Output is correct
16 Correct 1528 ms 12844 KB Output is correct
17 Correct 367 ms 12792 KB Output is correct
18 Correct 367 ms 12836 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 4 ms 376 KB Output is correct
4 Correct 16 ms 888 KB Output is correct
5 Correct 10 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 174 ms 9596 KB Output is correct
9 Correct 447 ms 5688 KB Output is correct
10 Correct 1454 ms 12504 KB Output is correct
11 Correct 372 ms 13020 KB Output is correct
12 Correct 362 ms 13088 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 176 ms 9592 KB Output is correct
15 Correct 79 ms 2180 KB Output is correct
16 Correct 1515 ms 12884 KB Output is correct
17 Correct 367 ms 12792 KB Output is correct
18 Correct 366 ms 12728 KB Output is correct
19 Correct 1556 ms 68340 KB Output is correct
20 Correct 1551 ms 65872 KB Output is correct
21 Correct 1575 ms 68460 KB Output is correct
22 Correct 1565 ms 66068 KB Output is correct
23 Correct 1547 ms 65900 KB Output is correct
24 Correct 1555 ms 65740 KB Output is correct
25 Correct 1551 ms 65784 KB Output is correct
26 Correct 1585 ms 68348 KB Output is correct
27 Correct 1562 ms 68320 KB Output is correct
28 Correct 1546 ms 65820 KB Output is correct
29 Correct 1548 ms 65768 KB Output is correct
30 Correct 1556 ms 65788 KB Output is correct