oj.uz

Submission #139555

# Submission time Handle Problem Language Result Execution time Memory
139555 2019-08-01T02:49:29 Z dcordb Wall (IOI14_wall) C++11
8 / 100
 3000 ms 102284 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int
	MAX = 1e6 + 5,
	INF = 1e6;
vector <int> lazy[4 * MAX];
int a[MAX];

vector <int> concat(const vector <int> &a, const vector <int> &b) {
	vector <int> v;
	for(auto o : a) v.push_back(o);
	for(auto o : b) v.push_back(o);
	return v;
}

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;
}

vector <int> tryReduce(vector <int> v) {
	for(int i = 0; i < (int) v.size() - 1; i++) {
		bool ok = true;
		int r = reduce(v[i], v[i + 1], ok);

		if(ok) {
			vector <int> aux;
			for(int j = 0; j < i; j++)
				aux.push_back(v[j]);

			aux.push_back(r);

			for(int j = i + 2; j < (int) v.size(); j++)
				aux.push_back(v[j]);

			return aux;
		}
	}

	return {};
}

int sgn(int x) { return (x >= 0) ? +1 : -1; }

void transform(int &a, int &b) {
	assert(sgn(a) != sgn(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;
		}
	}
}

vector <int> reduce(vector <int> v) {
	assert((int) v.size() <= 4);

	while((int) v.size() > 1) {
		auto r = tryReduce(v);

		if(r.empty()) {
			if((int) v.size() == 2)
				break;

			transform(v[0], v[1]);
		}

		else v = r;
	}

	assert((int) v.size() <= 2);

	return v;
}

void build(int x, int st, int nd) {
	lazy[x] = {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(st == nd) {
		for(auto o : lazy[x]) {
			if(o >= 0)
				a[st] = max(a[st], o);

			else a[st] = min(a[st], -o);
		}
	}

	else {
		lazy[2 * x] = reduce(concat(lazy[2 * x], lazy[x]));
		lazy[2 * x + 1] = reduce(concat(lazy[2 * x + 1], lazy[x]));
	}

	lazy[x] = {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};
		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 94 ms 94428 KB Output is correct
2 Correct 99 ms 94316 KB Output is correct
3 Correct 146 ms 94300 KB Output is correct
4 Correct 443 ms 95148 KB Output is correct
5 Correct 331 ms 95080 KB Output is correct
6 Correct 345 ms 95096 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 94288 KB Output is correct
2 Correct 296 ms 102120 KB Output is correct
3 Execution timed out 3024 ms 98860 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 94200 KB Output is correct
2 Correct 105 ms 94372 KB Output is correct
3 Correct 128 ms 94380 KB Output is correct
4 Correct 435 ms 95080 KB Output is correct
5 Correct 331 ms 95224 KB Output is correct
6 Correct 327 ms 95076 KB Output is correct
7 Correct 96 ms 94328 KB Output is correct
8 Correct 279 ms 102284 KB Output is correct
9 Execution timed out 3050 ms 98788 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 94336 KB Output is correct
2 Correct 91 ms 94328 KB Output is correct
3 Correct 128 ms 94428 KB Output is correct
4 Correct 432 ms 95132 KB Output is correct
5 Correct 432 ms 95096 KB Output is correct
6 Correct 341 ms 95088 KB Output is correct
7 Correct 89 ms 94228 KB Output is correct
8 Correct 282 ms 102236 KB Output is correct
9 Execution timed out 3039 ms 98840 KB Time limit exceeded
10 Halted 0 ms 0 KB -