oj.uz

Submission #39306

# Submission time Handle Problem Language Result Execution time Memory
39306 2018-01-11T05:51:09 Z mohammad_kilani Wall (IOI14_wall) C++14
0 / 100
 206 ms 56716 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define oo 2000000000
const int N = 2000010;
pair<int,int> seg[3 * 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<=3 * 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
0 / 8.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 48892 KB Output is correct
2 Correct 206 ms 56716 KB Output is correct
3 Incorrect 179 ms 52288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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