Submission #684547

#	Time	Username	Problem	Language	Result	Execution time	Memory
684547		fuad27	Wall (IOI14_wall)	C++17	100 / 100	1878 ms	99396 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "/home/fuad/cp/dbg.h"
#else
#define dbg(x...)
#endif

const int N = 2000010;
pair<int,int> T[4*N];
void updMn(int l, int r, int tl, int tr, int v, int p, int d);
void updMx(int l, int r, int tl, int tr, int v, int p, int d);
void updMn(int l, int r, int tl, int tr, int v, int p, int d=0) {
	if(l>r)return;
	if(l==tl and r==tr) {
		T[v].first=min(T[v].first,p);
		T[v].second=min(T[v].second,T[v].first);
		return;
	}
	int tm=(tl+tr)/2;
	updMn(tl,tm,tl,tm,2*v,T[v].first, 1);
	updMn(tm+1,tr,tm+1,tr,2*v+1,T[v].first, 1);
	updMx(tl,tm,tl,tm,2*v,T[v].second, 1);
	updMx(tm+1,tr,tm+1,tr,2*v+1,T[v].second, 1);
	T[v]={2e9,0};
	updMn(l,min(r,tm), tl, tm, 2*v, p);
	updMn(max(l,tm+1),r, tm+1, tr, 2*v+1, p);
}
void updMx(int l, int r, int tl, int tr, int v, int p, int d=0) {
	if(l>r)return;
	if(l==tl and r==tr) {
		T[v].second=max(T[v].second,p);
		T[v].first=max(T[v].first,T[v].second);
		return;
	}
	int tm=(tl+tr)/2;
	updMn(tl,tm,tl,tm,2*v,T[v].first, 1);
	updMn(tm+1,tr,tm+1,tr,2*v+1,T[v].first, 1);
	updMx(tl,tm,tl,tm,2*v,T[v].second, 1);
	updMx(tm+1,tr,tm+1,tr,2*v+1,T[v].second, 1);
	T[v]={2e9,0};
	updMx(l,min(r,tm), tl, tm, 2*v, p);
	updMx(max(l,tm+1),r, tm+1, tr, 2*v+1, p);
}
int get(int tl, int tr, int v, int p) {
	if(tl == tr and tl==p) {
		return min(T[v].first,T[v].second);
	}
	int tm=(tl+tr)/2;
	updMn(tl,tm,tl,tm,2*v,T[v].first, 1);
	updMn(tm+1,tr,tm+1,tr,2*v+1,T[v].first, 1);
	updMx(tl,tm,tl,tm,2*v,T[v].second, 1);
	updMx(tm+1,tr,tm+1,tr,2*v+1,T[v].second, 1);
	if(p<=tm) {
		return get(tl,tm,2*v,p);
	}
	return get(tm+1,tr,2*v+1,p);

}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i =0;i<4*N;i++)T[i]={2e9,0};
	for(int i = 0;i<k;i++) {
		if(op[i]==1) {
			updMx(left[i],right[i],0,n-1,1,height[i]);
		}
		else {
			updMn(left[i],right[i],0,n-1,1,height[i]);
		}
	}
	for(int i = 0;i<n;i++) {
		finalHeight[i]=get(0,n-1,1,i);
	}
}

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