Submission #703199

#	Time	Username	Problem	Language	Result	Execution time	Memory
703199		bane	Wall (IOI14_wall)	C++17	100 / 100	1651 ms	224560 KiB

wall

#include<bits/stdc++.h>
#include<wall.h>
using namespace std;
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define ll long long 
 
#ifdef LOCAL
    #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
    #define eprintf(...) 42
#endif
const int EX = (int)-1e9;
const int MAXN = 2000000*3;
pair<ll,ll> t[MAXN];
pair<ll,ll> lazy[MAXN]; //{max,min}
int n;
void propagate(int k, int l, int r){
	{
			t[k].fr = max(t[k].fr, lazy[k].fr);
			t[k].sc = max(t[k].sc, t[k].fr);
			if (l != r){
				lazy[k*2].fr = max(lazy[k*2].fr, lazy[k].fr);
				lazy[k*2].sc = max(lazy[k*2].sc, lazy[k*2].fr);
				lazy[k*2+1].fr = max(lazy[k*2+1].fr, lazy[k].fr);
				lazy[k*2+1].sc = max(lazy[k*2+1].sc, lazy[k*2+1].fr);
			}
			lazy[k].fr = EX;
	}
	{
		t[k].sc = min(t[k].sc, lazy[k].sc);
		t[k].fr = min(t[k].fr, t[k].sc);
		if (l!=r){
			lazy[k*2].sc = min(lazy[k*2].sc, lazy[k].sc);
			lazy[k*2].fr = min(lazy[k*2].fr, lazy[k*2].sc);
			lazy[k*2+1].sc = min(lazy[k*2+1].sc, lazy[k].sc);
			lazy[k*2+1].fr = min(lazy[k*2+1].fr, lazy[k*2+1].sc);
		}
		lazy[k].sc = -EX;
	}
}
void update(int a, int b, int inc, int v, int l = 0, int r = n - 1, int k = 1){
	propagate(k,l,r);
	if (l > b || r < a)return;
	if (l >= a && r <= b){
		if (inc)lazy[k].fr = v;
		else lazy[k].sc=v;
		propagate(k,l,r);
		return;
	}
	update(a,b,inc,v,l,(l+r)/2,k*2);
	update(a,b,inc,v,(l+r)/2+1,r,k*2+1);
}
int query(int a, int l = 0, int r = n - 1, int k=  1){
	propagate(k,l,r);
	if (l == r){
		return t[k].fr;
	}
	int m = (l + r)/2;
	if (a <= m)return query(a,l,m,k*2);
	else return query(a,m+1,r,k*2+1);
}
void buildWall(int nn, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	n = nn;
	for (int i = 0; i < MAXN;i++){
		t[i] = {EX, -EX};
		lazy[i]= {EX,-EX};
	}
	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] = max(0, query(i));
	}
}

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