oj.uz

Submission #211156

# Submission time Handle Problem Language Result Execution time Memory
211156 2020-03-19T10:31:00 Z mode149256 Wall (IOI14_wall) C++14
100 / 100
 1213 ms 224880 KB 
/*input

*/
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

struct node {
	int l, r;
	int low;
	int high;
	node *left = nullptr;
	node *right = nullptr;

	node(int a, int b): l(a), r(b) {
		low = 0;
		high = 0;
		if (l != r) {
			left = new node(l, (l + r) / 2);
			right = new node((l + r) / 2 + 1, r);
		}
	}

	inline void push() {
		if (l != r) {
			for (auto && chil : {left, right}) {
				chil->low = max(chil->low, low);
				chil->low = min(chil->low, high);

				chil->high = max(chil->high, low);
				chil->high = min(chil->high, high);
			}
		}
	}

	inline void fix() {
		if (l != r) {
			for (auto && chil : {left, right}) {
				low = min(chil->low, low);
				high = max(chil->high, high);
			}
		}
	}

	void addLow(int a, int b, int w) {
		push();
		if (r < a or b < l) return;
		else if (a <= l and r <= b) {
			low = max(low, w);
			high = max(high, low);
			return;
		} else {
			left->addLow(a, b, w);
			right->addLow(a, b, w);
		}
		fix();
	}

	void addHigh(int a, int b, int w) {
		push();
		if (r < a or b < l) return;
		else if (a <= l and r <= b) {
			high = min(high, w);
			low = min(high, low);
			return;
		} else {
			left->addHigh(a, b, w);
			right->addHigh(a, b, w);
		}
		fix();
	}

	void finish(int final[]) {
		push();
		if (l == r) {
			// printf("l = %d, r = %d, low = %d, high = %d\n", l, r, low, high);
			final[l] = low;
		} else {
			left->finish(final);
			right->finish(final);
		}
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	node medis(0, n - 1);
	for (int i = 0; i < k; ++i)
	{
		if (--op[i])
			medis.addHigh(left[i], right[i], height[i]);
		else
			medis.addLow(left[i], right[i], height[i]);
	}
	medis.finish(finalHeight);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 13 ms 1536 KB Output is correct
5 Correct 11 ms 1536 KB Output is correct
6 Correct 11 ms 1536 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 189 ms 14072 KB Output is correct
3 Correct 257 ms 9208 KB Output is correct
4 Correct 918 ms 27768 KB Output is correct
5 Correct 488 ms 28868 KB Output is correct
6 Correct 445 ms 27304 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 10 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 12 ms 1536 KB Output is correct
5 Correct 11 ms 1536 KB Output is correct
6 Correct 14 ms 1536 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 178 ms 13944 KB Output is correct
9 Correct 296 ms 9208 KB Output is correct
10 Correct 888 ms 27896 KB Output is correct
11 Correct 465 ms 28920 KB Output is correct
12 Correct 450 ms 27252 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 179 ms 13944 KB Output is correct
15 Correct 46 ms 3324 KB Output is correct
16 Correct 872 ms 28024 KB Output is correct
17 Correct 451 ms 27640 KB Output is correct
18 Correct 439 ms 27432 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 12 ms 1536 KB Output is correct
5 Correct 11 ms 1536 KB Output is correct
6 Correct 12 ms 1536 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 182 ms 14072 KB Output is correct
9 Correct 263 ms 9336 KB Output is correct
10 Correct 930 ms 27768 KB Output is correct
11 Correct 467 ms 28920 KB Output is correct
12 Correct 445 ms 27384 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 179 ms 13944 KB Output is correct
15 Correct 45 ms 3192 KB Output is correct
16 Correct 886 ms 28024 KB Output is correct
17 Correct 454 ms 27512 KB Output is correct
18 Correct 454 ms 27564 KB Output is correct
19 Correct 1196 ms 224668 KB Output is correct
20 Correct 1192 ms 222200 KB Output is correct
21 Correct 1169 ms 224584 KB Output is correct
22 Correct 1186 ms 222200 KB Output is correct
23 Correct 1185 ms 222328 KB Output is correct
24 Correct 1199 ms 222276 KB Output is correct
25 Correct 1213 ms 222148 KB Output is correct
26 Correct 1201 ms 224880 KB Output is correct
27 Correct 1190 ms 224832 KB Output is correct
28 Correct 1167 ms 222204 KB Output is correct
29 Correct 1207 ms 222408 KB Output is correct
30 Correct 1181 ms 222068 KB Output is correct