oj.uz

Submission #7282

# Submission time Handle Problem Language Result Execution time Memory
7282 2014-07-29T09:38:11 Z imsifile Wall (IOI14_wall) C++
0 / 100
 620 ms 32948 KB 
#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]=-1;
		else finalheight[i]=itr[1][0];
	}
}

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24732 KB Output is correct
2 Correct 4 ms 24732 KB Output is correct
3 Correct 4 ms 24732 KB Output is correct
4 Correct 4 ms 24732 KB Output is correct
5 Incorrect 4 ms 24732 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24732 KB Output is correct
2 Correct 420 ms 32556 KB Output is correct
3 Correct 228 ms 27980 KB Output is correct
4 Correct 620 ms 32948 KB Output is correct
5 Incorrect 520 ms 32948 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24732 KB Output is correct
2 Correct 4 ms 24732 KB Output is correct
3 Correct 0 ms 24732 KB Output is correct
4 Correct 4 ms 24732 KB Output is correct
5 Incorrect 4 ms 24732 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24732 KB Output is correct
2 Correct 4 ms 24732 KB Output is correct
3 Correct 0 ms 24732 KB Output is correct
4 Correct 4 ms 24732 KB Output is correct
5 Incorrect 4 ms 24732 KB Output isn't correct
6 Halted 0 ms 0 KB -