oj.uz

Submission #97363

# Submission time Handle Problem Language Result Execution time Memory
97363 2019-02-15T13:44:28 Z fefe Wall (IOI14_wall) C++17
100 / 100
 1658 ms 120568 KB 
#include "wall.h"
#include<bits/stdc++.h>
#define MAX_N 2000005
#define inf 1000005
using namespace std;
struct Tree{
	int l,r,x;
}t[4*MAX_N];
void add(int x,int v,int b){
	if(b==1){
		if(v<=t[x].l)	return;
		if(t[x].l<v && t[x].r>v){
			t[x].l=v;
			t[x].x=1;
			return;
		}
		t[x].l=t[x].r=v;
		t[x].x=0;
	}else{
		if(t[x].r<=v)	return;
		if(t[x].l<=v && t[x].r>v){
			t[x].r=v;
			t[x].x=0;
			return;
		}
		t[x].l=t[x].r=v;
		t[x].x=1;
	}
}
void spread(int x,int y){
	if(t[x].x){
		add(y,t[x].l,1);
		add(y,t[x].r,2);
	}else{
		add(y,t[x].r,2);
		add(y,t[x].l,1);
	}
}
void update(int x,int l,int r,int s,int e,int v,int b){
	if(l!=r){
		spread(x,2*x);
		spread(x,2*x+1);
		t[x]={0,inf,0};
	}
	if(e<l || r<s)	return;
	if(s<=l && r<=e){
		add(x,v,b);
		return;
	}
	int mid=(l+r)>>1;
	update(2*x,l,mid,s,e,v,b);
	update(2*x+1,mid+1,r,s,e,v,b);
}
int calc(int x,int v,int b){
	if(b==1)	return (x<v?v:x);
	else	return (x>v?v:x);
}
int get(int x,int l,int r,int p){
	if(l==r)	return t[x].l;
	int mid=(l+r)>>1,q;
	if(p<=mid)	q=get(2*x,l,mid,p);	
	else	q=get(2*x+1,mid+1,r,p);
	if(t[x].x==0)	q=calc(calc(q,t[x].l,1),t[x].r,2);
	else	q=calc(calc(q,t[x].r,2),t[x].l,1);
	return q;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	int i;
	for(i=0;i<=4*n;i++)	t[i]={0,inf,0};
	for(i=0;i<k;i++){
		update(1,0,n-1,left[i],right[i],height[i],op[i]);
	}
	for(i=0;i<n;i++)	finalHeight[i]=get(1,0,n-1,i);
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 16 ms 1024 KB Output is correct
5 Correct 10 ms 1024 KB Output is correct
6 Correct 11 ms 1024 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 226 ms 8688 KB Output is correct
3 Correct 357 ms 4900 KB Output is correct
4 Correct 1216 ms 13832 KB Output is correct
5 Correct 425 ms 14388 KB Output is correct
6 Correct 495 ms 14464 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 13 ms 1024 KB Output is correct
5 Correct 14 ms 1024 KB Output is correct
6 Correct 14 ms 1024 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 264 ms 8616 KB Output is correct
9 Correct 385 ms 4956 KB Output is correct
10 Correct 1164 ms 13804 KB Output is correct
11 Correct 567 ms 14376 KB Output is correct
12 Correct 462 ms 14428 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 267 ms 8568 KB Output is correct
15 Correct 77 ms 2200 KB Output is correct
16 Correct 1307 ms 14200 KB Output is correct
17 Correct 650 ms 14060 KB Output is correct
18 Correct 493 ms 14200 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 17 ms 1152 KB Output is correct
5 Correct 14 ms 1024 KB Output is correct
6 Correct 10 ms 1024 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 227 ms 8528 KB Output is correct
9 Correct 368 ms 4852 KB Output is correct
10 Correct 1260 ms 13892 KB Output is correct
11 Correct 455 ms 14200 KB Output is correct
12 Correct 514 ms 14268 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 223 ms 8696 KB Output is correct
15 Correct 73 ms 2268 KB Output is correct
16 Correct 1331 ms 14120 KB Output is correct
17 Correct 533 ms 14188 KB Output is correct
18 Correct 599 ms 14152 KB Output is correct
19 Correct 1438 ms 120452 KB Output is correct
20 Correct 1403 ms 118088 KB Output is correct
21 Correct 1487 ms 120568 KB Output is correct
22 Correct 1524 ms 117992 KB Output is correct
23 Correct 1525 ms 117996 KB Output is correct
24 Correct 1427 ms 118112 KB Output is correct
25 Correct 1460 ms 117940 KB Output is correct
26 Correct 1430 ms 120340 KB Output is correct
27 Correct 1590 ms 120412 KB Output is correct
28 Correct 1482 ms 118136 KB Output is correct
29 Correct 1440 ms 117912 KB Output is correct
30 Correct 1658 ms 117852 KB Output is correct