oj.uz

Submission #7283

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

Subtask #1
8.0 / 8.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 8 ms 24732 KB Output is correct
5 Correct 4 ms 24732 KB Output is correct
6 Correct 4 ms 24732 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24732 KB Output is correct
2 Correct 416 ms 32556 KB Output is correct
3 Correct 216 ms 27980 KB Output is correct
4 Correct 632 ms 32948 KB Output is correct
5 Correct 516 ms 32948 KB Output is correct
6 Correct 512 ms 32948 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24732 KB Output is correct
2 Correct 8 ms 24732 KB Output is correct
3 Correct 4 ms 24732 KB Output is correct
4 Correct 8 ms 24732 KB Output is correct
5 Correct 8 ms 24732 KB Output is correct
6 Correct 4 ms 24732 KB Output is correct
7 Correct 0 ms 24732 KB Output is correct
8 Correct 412 ms 32556 KB Output is correct
9 Correct 228 ms 27980 KB Output is correct
10 Correct 616 ms 32948 KB Output is correct
11 Correct 520 ms 32948 KB Output is correct
12 Correct 492 ms 32948 KB Output is correct
13 Correct 4 ms 24732 KB Output is correct
14 Correct 408 ms 32556 KB Output is correct
15 Correct 32 ms 25216 KB Output is correct
16 Correct 692 ms 32948 KB Output is correct
17 Correct 552 ms 32948 KB Output is correct
18 Correct 564 ms 32948 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24732 KB Output is correct
2 Correct 8 ms 24732 KB Output is correct
3 Correct 4 ms 24732 KB Output is correct
4 Correct 0 ms 24732 KB Output is correct
5 Correct 4 ms 24732 KB Output is correct
6 Correct 4 ms 24732 KB Output is correct
7 Correct 0 ms 24732 KB Output is correct
8 Correct 412 ms 32556 KB Output is correct
9 Correct 240 ms 27980 KB Output is correct
10 Correct 624 ms 32948 KB Output is correct
11 Correct 504 ms 32948 KB Output is correct
12 Correct 516 ms 32948 KB Output is correct
13 Correct 0 ms 24732 KB Output is correct
14 Correct 436 ms 32556 KB Output is correct
15 Correct 40 ms 25216 KB Output is correct
16 Correct 712 ms 32948 KB Output is correct
17 Correct 536 ms 32948 KB Output is correct
18 Correct 544 ms 32948 KB Output is correct
19 Correct 816 ms 40372 KB Output is correct
20 Correct 796 ms 40372 KB Output is correct
21 Correct 776 ms 40372 KB Output is correct
22 Correct 796 ms 40372 KB Output is correct
23 Correct 808 ms 40372 KB Output is correct
24 Correct 804 ms 40372 KB Output is correct
25 Correct 800 ms 40372 KB Output is correct
26 Correct 792 ms 40372 KB Output is correct
27 Correct 796 ms 40372 KB Output is correct
28 Correct 816 ms 40372 KB Output is correct
29 Correct 812 ms 40372 KB Output is correct
30 Correct 800 ms 40372 KB Output is correct