Submission #897515

#	Time	Username	Problem	Language	Result	Execution time	Memory
897515		oblantis	Wall (IOI14_wall)	C++17	61 / 100	340 ms	26716 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
const ll inf = 1e18 + 10000;
const int mod = 1e9+7;
const int maxn = 2e5 + 12;

int mx[maxn * 4], mn[maxn * 4], c[maxn * 4], xl, xr, x, wt, nw;
void rlx(int v){
	c[v * 2 + 1] = c[v * 2 + 2] = mn[v * 2 + 1] = mn[v * 2 + 2] = mx[v * 2 + 1] = mx[v * 2 + 2] = c[v];
	c[v] = -1;
}
void upd(int v, int l, int r){
	if(xr < l || r < xl)return;
	if(wt == 1 && mn[v] >= x)return;
	if(wt == 2 && mx[v] <= x)return;
	if(xl <= l && r <= xr){
		if(wt == 1 && mx[v] <= x){
			mx[v] = mn[v] = x;
			c[v] = x;
			return;
		}
		if(wt == 2 && mn[v] >= x){
			mn[v] = mx[v] = x;
			c[v] = x;
			return;
		}
	}
	if(c[v] != -1){
		rlx(v);
	}
	upd(v * 2 + 1, l, (l + r) / 2), upd(v * 2 + 2, (l + r) / 2 + 1, r);
	mn[v] = min(mn[v * 2 + 1], mn[v * 2 + 2]), mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}
int get(int v, int l, int r){
	if(l == r){
		return mn[v];
	}
	if(c[v] != -1)rlx(v);
	if((l + r) / 2 < nw)return get(v * 2 + 2, (l + r) / 2 + 1, r);
	else return get(v * 2 + 1, l, (l + r) / 2); 
}
void buildWall(int n, int k, int op[], int left[], int right[], int h[], int fh[]){
	for(int i = 0; i < n * 4; i++)c[i] = -1;
	for(int i = 0; i < k; i++){
		wt = op[i], xl = left[i], xr = right[i], x = h[i];
		upd(0, 0, n);
	}
	for(int i = 0; i < n; i++){
		nw = i;
		fh[i] = get(0, 0, n);
	}
	return;
}

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