Submission #485399

#	Time	Username	Problem	Language	Result	Execution time	Memory
485399		Eyed	Wall (IOI14_wall)	C++14	0 / 100	198 ms	137984 KiB

wall

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <climits>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll MOD = 1e9 + 7;

struct range {
	int l;
	int r;
	range(int xx = 0, int yy = 0) : l(xx), r(yy) {};
};

int nn, kk;
int tree[8000025];
range lazy[8000025];
bool mark[8000025];

void push(int v) {
	if (mark[v]) {
		if (lazy[v].r < lazy[2 * v].l) {
			lazy[2 * v].l = lazy[v].l;
			lazy[2 * v].r = lazy[v].r;
		}
		else if (lazy[v].l > lazy[2 * v].r) {
			lazy[2 * v].l = lazy[v].l;
			lazy[2 * v].r = lazy[v].r;
		}
		else {
			lazy[2 * v].l = max(lazy[2 * v].l, lazy[v].l);
			lazy[2 * v].r = min(lazy[2 * v].r, lazy[v].r);
		}
		if (lazy[v].r < lazy[2 * v+1].l) {
			lazy[2 * v+1].l = lazy[v].l;
			lazy[2 * v+1].r = lazy[v].r;
		}
		else if (lazy[v].l > lazy[2 * v+1].r) {
			lazy[2 * v+1].l = lazy[v].l;
			lazy[2 * v+1].r = lazy[v].r;
		}
		else {
			lazy[2 * v+1].l = max(lazy[2 * v+1].l, lazy[v].l);
			lazy[2 * v+1].r = min(lazy[2 * v+1].r, lazy[v].r);
		}
		mark[v] = false;
	}
}

void update(int v, int tl, int tr, int ll, int rr, int op, int x) {
	if (ll > rr) return;
	if (ll == tl && rr == tr) {
		if (op == 0) {
			lazy[v].l = max(lazy[v].l, x);
			lazy[v].r = max(lazy[v].r, lazy[v].l);
		}
		if (op == 1) {
			lazy[v].r = min(lazy[v].r, x);
			lazy[v].l = min(lazy[v].l, lazy[v].r);
		}
		mark[v] = true;
		return;
	}
	push(v);
	int pos = (tl + tr) / 2;
	update(2 * v, tl, pos, ll, min(pos, rr), op, x);
	update(2 * v + 1, pos + 1, tr, max(pos + 1, ll), rr, op, x);
}

int get(int v, int tl, int tr, int x) {
	if (tl == tr) {
		if (tree[x] < lazy[v].l) return lazy[v].l;
		if (tree[x] > lazy[v].r) return lazy[v].r;
		return tree[x];
	}
	push(v);
	int tm = (tl + tr) / 2;
	if (x <= tm) return get(2 * v, tl, tm, x);
	else return get(2 * v + 1, tm + 1, tr, x);
}
void update(int ll, int rr, int op, int x) { update(1, 0, 2 * nn + 2, ll, rr, op, x); }
int get(int x) { return get(1, 0, 2 * nn + 2, x); }

void buildWall(int n, int k, int op[], int left[], int right[],
	int height[], int finalHeight[]) {
	for (int i = 0; i < n; ++i) tree[i] = 0;
	for (int i = 0; i < n; ++i) {
		lazy[i].l = 0;
		lazy[i].r = 100005;
	}
	for (int i = 0; i < k; ++i) update(left[i], right[i], op[i] - 1, height[i]);
	for (int i = 0; i < n; ++i) finalHeight[i] = get(i);
	return;
}

//int main(int argc, char* argv[]) {
//	/*const char* FIN  = "sample.in";
//	const char* FOUT = "sample.out";
//	const char* inFile = argc > 1 ? argv[1] : FIN;
//	ifstream cin(inFile);
//	ofstream cout(FOUT);*/
//
//	//cin >> n >> k;
//	//for (int i = 0; i < n; ++i) cin >> tree[i];
//	//for (int i = 0; i < 8000005; ++i) {
//	//	lazy[i].l = 0;
//	//	lazy[i].r = 100005;
//	//}
//	//for (int i = 0; i < k; ++i) {
//	//	int o, ll, rr, x;
//	//	cin >> o >> ll >> rr >> x;
//	//	update(ll, rr, o, x);
//	//	//o == 0 means adding, o == 1 means removing
//	//}
//	//for (int i = 0; i < n; ++i) cout << get(i) << endl;
//
//
//	return 0;
//}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39