Submission #828944

#	Time	Username	Problem	Language	Result	Execution time	Memory
828944		Lobo	Wall (IOI14_wall)	C++17	100 / 100	905 ms	162368 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
#define pb push_back
const int maxk = 5e5+10;
const int maxn = 2e6+10;
const int inf = 1e9+10;
int tra[4*maxk], trb[4*maxk];
vector<int> adds[maxn], rems[maxn];

void build(int no, int l, int r) {
	tra[no] = -inf;
	trb[no] = inf;
	if(l == r) return;
	int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
}

void upd(int no, int l, int r, int pos, int newa, int newb) {
	if(l > pos || r < pos) return;
	if(l == r) {
		if(newa != -1) tra[no] = newa;
		if(newb != -1) trb[no] = newb;
		return;
	}
	int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
	upd(lc,l,mid,pos,newa,newb);
	upd(rc,mid+1,r,pos,newa,newb);
	tra[no] = max(tra[lc],tra[rc]);
	trb[no] = min(trb[lc],trb[rc]);
}

pair<int,pair<int,int>> find(int no, int l, int r, int maxa, int minb) {
	if(l == r) return mp(l+1,mp(maxa,minb));
	int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
	if(max(maxa,tra[rc]) < min(minb,trb[rc])) return find(lc,l,mid,max(maxa,tra[rc]),min(minb,trb[rc]));
	else return find(rc,mid+1,r,maxa,minb);
}

void buildWall(int n, int k, int op[], int lf[], int rg[], int h[], int finalHeight[]){
	for(int i = 0; i < k; i++) {
		adds[lf[i]].pb(i);
		rems[rg[i]].pb(i);
	}
	build(1,0,k);
	for(int i = 0; i < n; i++) {
		for(auto j : adds[i]) {
			if(op[j] == 1) {
				upd(1,0,k,j+1,h[j],-1);
			}
			else {
				upd(1,0,k,j+1,-1,h[j]);
			}
		}
		upd(1,0,k,0,0,0);

		auto aux = find(1,0,k,-inf,inf);

		int hcur;
		if(aux.fr-1 == 0) hcur = 0;
		else hcur = h[aux.fr-2];
		int maxa = aux.sc.fr;
		int minb = aux.sc.sc;

		hcur = min(hcur,minb);
		hcur = max(hcur,maxa);

		finalHeight[i] = hcur;

		for(auto j : rems[i]) {
			if(op[j] == 1) {
				upd(1,0,k,j+1,-inf,-1);
			}
			else {
				upd(1,0,k,j+1,-1,inf);
			}
		}
	}
}

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