oj.uz

Submission #139515

# Submission time Handle Problem Language Result Execution time Memory
139515 2019-07-31T23:26:41 Z dcordb Wall (IOI14_wall) C++11
8 / 100
 3000 ms 108024 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair <char, int> op;
const int MAX = 1e6 + 5;
vector <op> lazy[4 * MAX];
int a[MAX];

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

vector <op> reduce(const op &a, const op &b) {
	int x = a.second;
	int y = b.second;

	if(b.first == 's')
		return {b};

	if(a.first == 's') {
		if(b.first == 'm') {
			if(x <= y)
				return {op('s', x)};

			return {op('s', y)};
		}

		else {
			assert(b.first == 'M');

			if(x <= y)
				return {op('s', y)};

			return {op('s', x)};
		}
	}

	if(a.first == 'm' && b.first == 'm') {
		if(x <= y)
			return {a};

		return {b};
	}

	if(a.first == 'M' && b.first == 'M') {
		if(x <= y)
			return {b};
		return {a};
	}

	if(a.first == 'm' && b.first == 'M') {
		if(x <= y)
			return {op('s', y)};
		return {a, b};
	}

	assert(a.first == 'M' && b.first == 'm');

	if(x <= y)
		return {a, b};

	return {op('s', y)};
}

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

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

			aux.push_back(r[0]);

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

			return aux;
		}
	}

	return {};
}

vector <op> reduce(vector <op> v) {
	if((int) v.size() == 1)
		return v;

	vector <op> r = tryReduce(v);

	if(r.empty()) { //no pudo reducir
		if((int) v.size() == 2)
			return v;

		swap(v[0], v[1]);
		return reduce(v);
	}

	return reduce(r);
}

void build(int x, int st, int nd) {
	lazy[x].push_back(op('M', 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) {
		auto r = reduce(concat({op('s', a[st])}, lazy[x]));
		assert((int) r.size() == 1);
		a[st] = r[0].second;
	}

	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] = {op('M', 0)};
}

void upd(int x, int st, int nd, int a, int b, const op &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++) {
		if(operation[i] == 1)
			upd(1, 0, n - 1, l[i], r[i], op('M', h[i]));

		else upd(1, 0, n - 1, l[i], r[i], op('m', h[i]));
	}

	for(int i = 0; i < n; i++) {
		upd(1, 0, n - 1, i, i, op('M', 0));
		ans[i] = a[i];
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 94328 KB Output is correct
2 Correct 94 ms 94456 KB Output is correct
3 Correct 131 ms 94328 KB Output is correct
4 Correct 431 ms 95204 KB Output is correct
5 Correct 382 ms 95196 KB Output is correct
6 Correct 399 ms 95232 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 94284 KB Output is correct
2 Correct 571 ms 108024 KB Output is correct
3 Execution timed out 3021 ms 102524 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 94276 KB Output is correct
2 Correct 94 ms 94456 KB Output is correct
3 Correct 132 ms 94328 KB Output is correct
4 Correct 444 ms 95196 KB Output is correct
5 Correct 377 ms 95316 KB Output is correct
6 Correct 382 ms 95224 KB Output is correct
7 Correct 92 ms 94276 KB Output is correct
8 Correct 560 ms 107996 KB Output is correct
9 Execution timed out 3038 ms 102540 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 94200 KB Output is correct
2 Correct 103 ms 94424 KB Output is correct
3 Correct 149 ms 94328 KB Output is correct
4 Correct 450 ms 95292 KB Output is correct
5 Correct 376 ms 95224 KB Output is correct
6 Correct 385 ms 95196 KB Output is correct
7 Correct 90 ms 94328 KB Output is correct
8 Correct 573 ms 107996 KB Output is correct
9 Execution timed out 3049 ms 102520 KB Time limit exceeded
10 Halted 0 ms 0 KB -