Submission #430811

#	Time	Username	Problem	Language	Result	Execution time	Memory
430811		CSQ31	Wall (IOI14_wall)	C++17	100 / 100	1477 ms	167212 KiB

wall

#include "wall.h"
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 2e6+2;
vector<ll>mn(4*MAXN,INF),mx(4*MAXN,-INF);
vector<ll>ans(MAXN);
//each operation can be reduced to one max and min operation,call it x and y where y <=x (min first then max
//induction : 
//case 1: max opt with height h
//if(x<= h <= y) x=h
//if(h < x) do nothing
//if(y < h)x=y=h
//case 2 : min opt with height h
//if(x <= h <= y)y=h;
//if(y<h)do nothing
//if(x<h) x=y=h;
void apply(int a,int b){ //apply node a to node b
	mn[b] = min(mn[b],mn[a]);
	mx[b] = min(mx[b],mn[a]);
	mn[b] = max(mn[b],mx[a]);
	mx[b] = max(mx[b],mx[a]);	
}

void pushdown(int v){
	apply(v,2*v);
	apply(v,2*v+1);
	mn[v] = INF;
	mx[v] = -INF;
	
}
void upd(int v,int l,int r,int tl,int tr,ll v0,ll v1){
	if(l>r)return;
	if(tl!=tr)pushdown(v);
	if(l==tl && r==tr){
	    mn[v] = min(mn[v],v0);
	    mx[v] = min(mx[v],v0);
	    mn[v] = max(mn[v],v1);
	    mx[v] = max(mx[v],v1);
		return;
	}
	int tm = (tl+tr)/2;
	upd(2*v,l,min(r,tm),tl,tm,v0,v1);
	upd(2*v+1,max(tm+1,l),r,tm+1,tr,v0,v1);
}
void query(int v,int l,int r){
	if(l==r){
		ll res = 0;
		res = min(res,mn[v]);
		res = max(res,mx[v]);
		ans[l-1] = res;
		return;
	}
	int tm = (l+r)/2;
	pushdown(v);
	query(2*v,l,tm);
	query(2*v+1,tm+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<k;i++){
		ll v0 = INF;
		ll v1 = -INF;
		if(op[i] == 1)v1 = height[i];
		else v0 = height[i];
		
		upd(1,left[i]+1,right[i]+1,1,n,v0,v1);
		//cout<<"CUR:"<<i<<'\n';
		//print(1,1,n);
	}
	query(1,1,n);
	for(int i=0;i<n;i++)finalHeight[i] = ans[i];
}

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