Submission #17240

#	Time	Username	Problem	Language	Result	Execution time	Memory
17240		erdemkiraz	Wall (IOI14_wall)	C++98	100 / 100	1157 ms	118924 KiB

wall

#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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39