oj.uz

Submission #17240

# Submission time Handle Problem Language Result Execution time Memory
17240 2015-11-09T18:15:05 Z erdemkiraz Wall (IOI14_wall) C++
100 / 100
 1157 ms 118924 KB 
#include "wall.h"

#include <algorithm>
#include <iostream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define F first
#define S second

#define endl '\n'

#define mp make_pair
#define pb push_back

#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)

#define type(x) __typeof((x).begin())
#define foreach(i, x) for(type(x) i = (x).begin(); i != (x).end(); i++)

#define sol (root + root)
#define sag (root + root + 1)
#define orta ((bas + son) >> 1)

#define bit __builtin_popcount

#ifndef D
    #define dbg(x) 0
    #define dbgs(x) 0
#else
    #define dbg(x) cerr << (#x) << " --> " << (x) << endl
    #define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#endif

typedef long long ll;
typedef pair < int, int > pii;

const int inf = 1e9 + 5;
const ll linf = 1e18 + 5;

const int N = 2000000 + 5;

class node{

	public:

	int l, r, w;

	node() {
		l = r = -1;
		w = 0;
	}

};

int n, m, type, x, y, k, a[N];
node kd[N << 2];

node make(int l, int r, int w) {

	node t;
	t.l = l;
	t.r = r;
	t.w = w;
	return t;

}

node max_here(int root, int k) {

	if(kd[root].r == -1) {
		if(kd[root].l != -1 and k < kd[root].l)
			return kd[root];
		return kd[root] = make(k, -1, 0);
	}
	if(kd[root].l == -1)
		return kd[root] = make(k, max(k, kd[root].r), 0);
	return kd[root] = make(max(k, kd[root].l), max(kd[root].r, max(k, kd[root].l)), 0);

}

node min_here(int root, int k) {

	if(kd[root].l == -1) {
		if(kd[root].r != -1 and k > kd[root].r)
			return kd[root];
		return kd[root] = make(-1, k, 1);
	}
	if(kd[root].r == -1)
		return kd[root] = make(min(k, kd[root].l), k, 1);
	return kd[root] = make(min(kd[root].l, min(k, kd[root].r)), min(k, kd[root].r), 1);

}

void push(int root) {

	if(kd[root].w == 0) {
		if(kd[root].r != -1) {
			min_here(sol, kd[root].r);
			min_here(sag, kd[root].r);
		}
		if(kd[root].l != -1) {
			max_here(sol, kd[root].l);
			max_here(sag, kd[root].l);
		}
	}
	else {
		if(kd[root].l != -1) {
			max_here(sol, kd[root].l);
			max_here(sag, kd[root].l);
		}
		if(kd[root].r != -1) {
			min_here(sol, kd[root].r);
			min_here(sag, kd[root].r);
		}
	}

	kd[root].l = -1;
	kd[root].r = -1;
	kd[root].w = 0;

}

void upmax(int root, int bas, int son, int x, int y, int k) {

	if(son < x or y < bas)
		return;

	if(x <= bas and son <= y) {
		max_here(root, k);
		return;
	}

	push(root);

	upmax(sol, bas, orta, x, y, k);
	upmax(sag, orta + 1, son, x, y, k);

}

void upmin(int root, int bas, int son, int x, int y, int k) {

	if(son < x or y < bas)
		return;

	if(x <= bas and son <= y) {
		min_here(root, k);
		return;
	}

	push(root);

	upmin(sol, bas, orta, x, y, k);
	upmin(sag, orta + 1, son, x, y, k);

}

void calc(int root, int bas, int son) {

	if(bas == son) {
		a[bas] = kd[root].l;
		return;
	}

	push(root);
	calc(sol, bas, orta);
	calc(sag, orta + 1, son);

}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	:: n = n;
	:: m = k;
	for(int i = 0; i < k; i++) {
		int type = op[i];
		int x = left[i] + 1;
		int y = right[i] + 1;
		int k = height[i];
		if(type == 1)
			upmax(1, 1, n, x, y, k);
		else
			upmin(1, 1, n, x, y, k);
	}
	calc(1, 1, n);
	FOR(i, 1, n) {
		if(a[i] == -1)
			a[i] = 0;
		finalHeight[i - 1] = a[i];
	}
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 103284 KB Output is correct
2 Correct 33 ms 103284 KB Output is correct
3 Correct 18 ms 103284 KB Output is correct
4 Correct 42 ms 103284 KB Output is correct
5 Correct 30 ms 103284 KB Output is correct
6 Correct 38 ms 103284 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 103284 KB Output is correct
2 Correct 50 ms 111108 KB Output is correct
3 Correct 295 ms 106532 KB Output is correct
4 Correct 875 ms 111500 KB Output is correct
5 Correct 438 ms 111500 KB Output is correct
6 Correct 393 ms 111500 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 103284 KB Output is correct
2 Correct 0 ms 103284 KB Output is correct
3 Correct 34 ms 103284 KB Output is correct
4 Correct 43 ms 103284 KB Output is correct
5 Correct 38 ms 103284 KB Output is correct
6 Correct 4 ms 103284 KB Output is correct
7 Correct 27 ms 103284 KB Output is correct
8 Correct 145 ms 111108 KB Output is correct
9 Correct 302 ms 106532 KB Output is correct
10 Correct 907 ms 111500 KB Output is correct
11 Correct 403 ms 111500 KB Output is correct
12 Correct 370 ms 111500 KB Output is correct
13 Correct 27 ms 103284 KB Output is correct
14 Correct 235 ms 111108 KB Output is correct
15 Correct 97 ms 103768 KB Output is correct
16 Correct 1142 ms 111500 KB Output is correct
17 Correct 416 ms 111500 KB Output is correct
18 Correct 427 ms 111500 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 103284 KB Output is correct
2 Correct 12 ms 103284 KB Output is correct
3 Correct 34 ms 103284 KB Output is correct
4 Correct 21 ms 103284 KB Output is correct
5 Correct 12 ms 103284 KB Output is correct
6 Correct 38 ms 103284 KB Output is correct
7 Correct 23 ms 103284 KB Output is correct
8 Correct 90 ms 111108 KB Output is correct
9 Correct 320 ms 106532 KB Output is correct
10 Correct 883 ms 111500 KB Output is correct
11 Correct 448 ms 111500 KB Output is correct
12 Correct 360 ms 111500 KB Output is correct
13 Correct 17 ms 103284 KB Output is correct
14 Correct 182 ms 111108 KB Output is correct
15 Correct 96 ms 103768 KB Output is correct
16 Correct 1157 ms 111500 KB Output is correct
17 Correct 415 ms 111500 KB Output is correct
18 Correct 356 ms 111500 KB Output is correct
19 Correct 980 ms 118924 KB Output is correct
20 Correct 997 ms 118924 KB Output is correct
21 Correct 1059 ms 118924 KB Output is correct
22 Correct 962 ms 118924 KB Output is correct
23 Correct 973 ms 118924 KB Output is correct
24 Correct 975 ms 118924 KB Output is correct
25 Correct 923 ms 118924 KB Output is correct
26 Correct 1025 ms 118924 KB Output is correct
27 Correct 992 ms 118924 KB Output is correct
28 Correct 945 ms 118924 KB Output is correct
29 Correct 989 ms 118924 KB Output is correct
30 Correct 1032 ms 118924 KB Output is correct