Submission #735768

#	Time	Username	Problem	Language	Result	Execution time	Memory
735768		vjudge1	Wall (IOI14_wall)	C++17	0 / 100	797 ms	65888 KiB

wall

#include<bits/stdc++.h>

using namespace std;

struct segTree1{
	vector<pair<int, int>> upd;
	int siz;
	void init(int n){
		siz = 1;
		while(siz < n) siz *= 2;
		upd.assign(2 * siz, {0, -1});
	}
	void set(int l, int r, int u, int t, int x, int lx, int rx){
		if(lx >= l && rx <= r){
			upd[x] = {u, t};
			return;
		}else if(lx >= r || rx <= l) return;
		int m = (lx + rx) / 2;
		set(l, r, u, t, 2 * x + 1, lx, m);
		set(l, r, u, t, 2 * x + 2, m, rx);
	}
	void set(int l, int r, int u, int t){
		set(l, r, u, t, 0, 0, siz);
	}
	pair<int, int> calc(int i, int x, int lx, int rx){
		if(rx - lx == 1){
			return upd[x];
		}
		int m = (lx + rx) / 2;
		pair<int, int> p;
		if(i < m) p = calc(i, 2 * x + 1, lx, m);
		else p = calc(i, 2 * x + 2, m, rx);
		if(upd[x].second > p.second){//Bigger numbers are more recent as I start from 1.
			return upd[x];
		}else return p;
	}
	int calc(int i){
		return calc(i, 0, 0, siz).first;
	}
};

struct segTree2{
	vector<int> mn;
	vector<int> mx;
	int siz;
	void init(int n){
		siz = 1;
		while(siz < n) siz *= 2;
		mn.assign(2 * siz, 1e9);
		mx.assign(2 * siz, 0);
	}
	void set(int i, int u, int x, int lx, int rx){
		if(rx - lx == 1){
			mn[x] = u; mx[x] = u;
			return;
		}
		int m = (lx + rx) / 2;
		if(i < m) set(i, u, 2 * x + 1, lx, m);
		else set(i, u, 2 * x + 2, m, rx);
		mn[x] = min(mn[2 * x + 1], mn[2 * x + 2]);
		mx[x] = max(mx[2 * x + 1], mx[2 * x + 2]);
	}
	void set(int i, int u){
		set(i, u, 0, 0, siz);
	}
	
	int calc_mx(int l, int u, int x, int lx, int rx){
		if(mx[x] <= u) return 1e9;
		if(rx - lx == 1) return lx;
		int m = (lx + rx) / 2;
		int ans = 1e9;
		if(l < m && mx[2 * x + 1] > u) ans = calc_mx(l, u, 2 * x + 1, lx, m);
		if(ans == 1e9) ans = calc_mx(l, u, 2 * x + 2, m, rx);
		return ans;
	}
	
	int calc_mx(int l, int u){
		return calc_mx(l, u, 0, 0, siz);
	}
	
	int calc_mn(int l, int u, int x, int lx, int rx){
		if(mn[x] >= u) return 1e9;
		if(rx - lx == 1) return lx;
		int m = (lx + rx) / 2;
		int ans = 1e9;
		if(l < m && mn[2 * x + 1] < u) ans = calc_mn(l, u, 2 * x + 1, lx, m);
		if(ans == 1e9) ans = calc_mn(l, u, 2 * x + 2, m, rx);
		return ans;
	}
	
	int calc_mn(int l, int u){
		return calc_mn(l, u, 0, 0, siz);
	}
};

segTree1 st; 
segTree2 st_mn, st_mx;

void ins(int x, int h, set<int>& curr, int type, int k, int cnt){
	auto it = curr.upper_bound(x);
	if((int)curr.size() == 0 || it == curr.begin()){
		if(type == 2) h = 0;
		int ind = min(st_mn.calc_mn(x + 1, h), st_mx.calc_mx(x + 1, h));
		if(ind == 1e9) ind = k + 1;
		st.set(x, ind, h, cnt);
	}else{
		it--;
		if(type == 1) h = max(h, st.calc(*it));
		else h = min(h, st.calc(*it));
		int ind = min(st_mn.calc_mn(x + 1, h), st_mx.calc_mx(x + 1, h));
		if(ind == 1e9) ind = k + 1;
		st.set(x, ind, h, cnt);
	}
}

void buildWall(int n, int k, int* op, int* left, int* right, int* height, int* finalHeight){
	st.init(k+1);
	st_mn.init(k+1);
	st_mx.init(k+1);
	vector<vector<int>> add(n);
	vector<vector<int>> eras(n);
	for(int i = 0; i < k; i++){
		add[left[i]].push_back(i+1);
		eras[right[i]].push_back(i+1);
	}
	set<int> curr;
	int cnt = 1;
	for(int i = 0; i < n; i++){
		if(i > 0){
			for(int x : eras[i-1]){
				auto it = curr.lower_bound(x);
				if(it == curr.begin()){
					ins(0, 0, curr, 0, k, cnt); cnt++;
				}else{
					it--;
					ins(*it, height[*it - 1], curr, op[x-1], k, cnt); cnt++;				
				}
				curr.erase(x);
			}
		}
		for(int x : add[i]){
			ins(x, height[x-1], curr, op[x-1], k, cnt); cnt++;
			curr.insert(x);
			if(op[x] == 1) st_mx.set(x, height[x-1]);
			else st_mn.set(x, height[x-1]);
		}
		finalHeight[i] = st.calc(k);
	}
}

//~ int main(){
	//~ int n, 
//~ }

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