oj.uz

Submission #39307

# Submission time Handle Problem Language Result Execution time Memory
39307 2018-01-11T05:52:45 Z mohammad_kilani Wall (IOI14_wall) C++14
100 / 100
 803 ms 80156 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define oo 2000000000
const int N = 2000010;
pair<int,int> seg[4 * N];

void update(int s,int e,int idx,int l,int r,int val,bool b){
	val = max(val,seg[idx].first);
	val = min(val,seg[idx].second);
	if(s > r || e < l) return;
	if(s >= l && e <= r){
		if(!b) seg[idx].first = val; else seg[idx].second = val;
		return;
	}
	update(s,(s+e)/2,idx*2,l,r,val,b);
	update((s+e)/2+1,e,idx*2+1,l,r,val,b);
}

void make(int s,int e,int idx,int cur,int *arr){
	cur = max(cur,seg[idx].first);
	cur = min(cur,seg[idx].second);
	if(s == e){
		arr[s] = cur;
		return;
	}
	make(s,(s+e)/2,idx*2,cur,arr);
	make((s+e)/2+1,e,idx*2+1,cur,arr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=1;i<=4 * n;i++) seg[i] = make_pair(0,oo);
	for(int i=k-1;i>=0;i--)
		update(0,n-1,1,left[i],right[i],height[i],op[i]-1);
	make(0,n-1,1,0,finalHeight);
  	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 64516 KB Output is correct
2 Correct 3 ms 64652 KB Output is correct
3 Correct 0 ms 64516 KB Output is correct
4 Correct 3 ms 64652 KB Output is correct
5 Correct 3 ms 64652 KB Output is correct
6 Correct 6 ms 64652 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 64516 KB Output is correct
2 Correct 203 ms 72340 KB Output is correct
3 Correct 176 ms 67912 KB Output is correct
4 Correct 526 ms 72732 KB Output is correct
5 Correct 353 ms 72732 KB Output is correct
6 Correct 343 ms 72732 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 64516 KB Output is correct
2 Correct 0 ms 64652 KB Output is correct
3 Correct 0 ms 64516 KB Output is correct
4 Correct 6 ms 64652 KB Output is correct
5 Correct 3 ms 64652 KB Output is correct
6 Correct 3 ms 64652 KB Output is correct
7 Correct 0 ms 64516 KB Output is correct
8 Correct 203 ms 72340 KB Output is correct
9 Correct 163 ms 67912 KB Output is correct
10 Correct 543 ms 72732 KB Output is correct
11 Correct 346 ms 72732 KB Output is correct
12 Correct 283 ms 72732 KB Output is correct
13 Correct 0 ms 64516 KB Output is correct
14 Correct 186 ms 72340 KB Output is correct
15 Correct 33 ms 65144 KB Output is correct
16 Correct 493 ms 72732 KB Output is correct
17 Correct 339 ms 72732 KB Output is correct
18 Correct 293 ms 72732 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 64516 KB Output is correct
2 Correct 0 ms 64652 KB Output is correct
3 Correct 0 ms 64516 KB Output is correct
4 Correct 3 ms 64652 KB Output is correct
5 Correct 3 ms 64652 KB Output is correct
6 Correct 3 ms 64652 KB Output is correct
7 Correct 0 ms 64516 KB Output is correct
8 Correct 193 ms 72340 KB Output is correct
9 Correct 179 ms 67912 KB Output is correct
10 Correct 479 ms 72732 KB Output is correct
11 Correct 313 ms 72732 KB Output is correct
12 Correct 323 ms 72732 KB Output is correct
13 Correct 0 ms 64516 KB Output is correct
14 Correct 176 ms 72340 KB Output is correct
15 Correct 19 ms 65144 KB Output is correct
16 Correct 489 ms 72732 KB Output is correct
17 Correct 313 ms 72732 KB Output is correct
18 Correct 269 ms 72732 KB Output is correct
19 Correct 719 ms 80156 KB Output is correct
20 Correct 729 ms 80156 KB Output is correct
21 Correct 683 ms 80156 KB Output is correct
22 Correct 779 ms 80156 KB Output is correct
23 Correct 719 ms 80156 KB Output is correct
24 Correct 803 ms 80156 KB Output is correct
25 Correct 786 ms 80156 KB Output is correct
26 Correct 649 ms 80156 KB Output is correct
27 Correct 743 ms 80156 KB Output is correct
28 Correct 723 ms 80156 KB Output is correct
29 Correct 659 ms 80156 KB Output is correct
30 Correct 726 ms 80156 KB Output is correct