Submission #7283

#	Time	Username	Problem	Language	Result	Execution time	Memory
7283		imsifile	Wall (IOI14_wall)	C++98	100 / 100	816 ms	40372 KiB

wall

#include "wall.h"
#include<algorithm>
#include<memory.h>
#define mi(a,b) (a<b?a:b)
#define mx(a,b) (a>b?a:b)
using namespace std;

struct dp {
	int ix, x, y, op; // op - 0:erase, 1:plus, 2:minus
	bool operator< (const dp& c) const {
		if(x!=c.x)return x<c.x;
		return ix<c.ix;
	}
}ba[1001001];

int cnt, j2, itr[1024290][2], ims, ime, mh;

void comb(int s1, int e1, int s2, int e2){
	if(s1==-1)ims=s2, ime=e2;
	else if(s2==-1)ims=s1, ime=e1;
	else if(e1<s2)ims=ime=s2;
	else if(e2<s1)ims=ime=e2;
	else ims=mx(s1,s2), ime=mi(e1,e2);
}

void ins(int ix, int s, int e){
	itr[ix][0]=s, itr[ix][1]=e, ix/=2;
	while(ix){
		comb(itr[ix*2][0], itr[ix*2][1], itr[ix*2+1][0], itr[ix*2+1][1]);
		itr[ix][0]=ims, itr[ix][1]=ime;
		ix/=2;
	}
}

void buildWall(int n, int k, int *op, int *left, int *right, int *height, int *finalheight){
	int i, j;
	for(j2=1; j2<k; j2*=2);
	for(i=0; i<k; i++){
		if(mh<height[i])mh=height[i];
		ba[cnt].x=left[i], ba[cnt].y=height[i];
		ba[cnt].ix=i, ba[cnt++].op=op[i];
		ba[cnt].x=right[i]+1, ba[cnt].y=height[i];
		ba[cnt].ix=i, ba[cnt++].op=0;
	}
	sort(ba,ba+cnt);
	memset(itr,-1,sizeof(itr));
	for(i=j=0; i<n; i++){
		for(; j<cnt; j++){
			if(ba[j].x>i)break;
			if(ba[j].op==0)ins(j2+ba[j].ix, -1, -1);
			else if(ba[j].op==1)ins(j2+ba[j].ix, ba[j].y, mh);
			else ins(j2+ba[j].ix, 0, ba[j].y);
		}
		if(itr[1][0]==-1)finalheight[i]=0;
		else finalheight[i]=itr[1][0];
	}
}

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