Submission #935162

#	Time	Username	Problem	Language	Result	Execution time	Memory
935162		zhasyn	Wall (IOI14_wall)	C++14	100 / 100	564 ms	84160 KiB

wall

#include <bits/stdc++.h>
#include <wall.h>
#define pii pair <int, int>
#define pb push_back
#define F first
#define S second
using namespace std;
const int N = 8 * 1e6 + 10;
int over[N];
struct segtree {
	vector <pii> tree;
	vector <int> orin;
	int sz;
	void init(int n){
		sz = 1;
		while(sz < n) sz *= 2;
		tree.assign(2 * sz - 1, {-1, INT_MAX});
		orin.assign(2 * sz - 1, 0);
	}
	void make(int x, int nt){
		//cout << x << " was\n";
		//cout << tree[x].F << " "<< tree[x].S << " "<< orin[x] << endl;
		//cout << tree[nt].F << " "<< tree[nt].S << " "<< orin[x] << endl;
		if(tree[x].F >= tree[nt].S){
			tree[nt] = tree[x];
			orin[nt] = 1;	
		} else{
			if(tree[x].S <= tree[nt].F){
				tree[nt] = tree[x];
				orin[nt] = 2;
			} else{
				tree[nt].F = max(tree[nt].F, tree[x].F);
				tree[nt].S = min(tree[nt].S, tree[x].S);
			}
		}
		//cout << tree[nt].F << " " << tree[nt].S << " " << orin[nt] << endl;
	}
	
	void prop(int x, int lx, int rx){
		if(rx - lx == 1) return;
		if(orin[x] != 0){
			orin[2 * x + 1] = orin[2 * x + 2] = orin[x];
			tree[2 * x + 1] = tree[2 * x + 2] = tree[x];
		} else{
			make(x, 2 * x + 1);
			make(x, 2 * x + 2);
		}
		
		orin[x] = 0;
		tree[x] = {-1, INT_MAX};
	}
	void upd(int l, int r, int code, int val, int x, int lx, int rx){
		if(l >= rx || lx >= r) return;
		if(l <= lx && rx <= r){
			//cout << tree[x].F << " " << tree[x].S << " " << orin[x] << endl;
			if((code == 1 && val >= tree[x].S) || (code == 2 && val <= tree[x].F)){
				orin[x] = code;
				if(code == 1) tree[x] = {val, INT_MAX};
				else tree[x] = {-1, val};
			} else{
				if(code == 1 && orin[x] <= 1) tree[x].F = max(tree[x].F, val);
				if(code == 2 && (orin[x] == 0 || orin[x] == 2)) tree[x].S = min(tree[x].S, val);
			}
			//cout << x << " "<< lx << " "<< rx << " "<< tree[x].F << " " << tree[x].S << " "<< orin[x] << endl;
			return;
		}
		prop(x, lx, rx);
		int mid = (lx + rx) / 2;
		upd(l, r, code, val, 2 * x + 1, lx, mid);
		upd(l, r, code, val, 2 * x + 2, mid, rx);
	}
	void upd(int l, int r, int code, int val){
		upd(l, r, code, val, 0, 0, sz);
	}
	void get(int x, int lx, int rx, pii nt, int ntt){
		if(ntt != 0){
			tree[x] = nt;
			orin[x] = ntt;
		} else{
			if(nt.F >= tree[x].S){
				tree[x] = nt;
				orin[x] = 1;
			} else{
				if(nt.S <= tree[x].F){
					tree[x] = nt;
					orin[x] = 2;
				} else{
					tree[x].F = max(tree[x].F, nt.F);
					tree[x].S = min(tree[x].S, nt.S);
				}
			}
		}
		if(rx - lx == 1){
			//if(orin[x] == 0) over[lx] = -1;
			if(orin[x] <= 1) over[lx] = max(0, tree[x].F);
			if(orin[x] == 2) over[lx] = tree[x].S;
			return;
		}
		int mid = (lx + rx) / 2;
		get(2 * x + 1, lx, mid, tree[x], orin[x]);
		get(2 * x + 2, mid, rx, tree[x], orin[x]);
	}
	void get(){
		get(0, 0, sz, {-1, INT_MAX}, 0);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[],
int h[], int ans[]){
	for(int i = 0; i < n; i++){
		ans[i] = 0;
	}
	segtree obj;
	obj.init(n);
	for(int i = 0; i < k; i++){
		obj.upd(left[i], right[i] + 1, op[i], h[i]);
		//cout << endl;
	}
	obj.get();
	for(int i = 0; i < n; i++){
		ans[i] = over[i];
	}
}
// int main (){
	// int n, k;
	// cin >> n >> k;
	// int op[k], left[k], right[k], h[k], ans[n];
	// for(int i = 0; i < k; i++){
		// cin >> op[i] >> left[i] >> right[i] >> h[i];
	// }
	// buildWall(n, k, op, left, right, h, ans);
	// for(int i = 0; i < n; i++){
		// cout << ans[i] << " ";
	// }
	// return 0;
// }

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