oj.uz

Submission #97256

# Submission time Handle Problem Language Result Execution time Memory
97256 2019-02-14T16:01:34 Z figter001 Wall (IOI14_wall) C++14
0 / 100
 16 ms 16896 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = (1<<22);

int mx[maxn],mn[maxn];
int l,r,val,t,h[maxn];

void pro(int n){
	if(t == 1){
		mx[n] = max(mx[n],val);
		mn[n] = max(mn[n],val);
	}else{
		mx[n] = min(mx[n],val);
		mn[n] = min(mn[n],val);
	}
}

void pro(int n,int s,int e){
	mn[n] = min(mn[n],mn[n/2]);
	mn[n] = max(mn[n],mx[n/2]);
	mx[n] = max(mx[n],mx[n/2]);
	mx[n] = min(mx[n],mn[n/2]);
}

void update(int n,int s,int e){
	if(s > r || e < l)return;
	if(s >= l && e <= r){
		pro(n);
		return;
	}
	pro(n*2,s,e);
	pro(n*2+1,s,e);
	mn[n] = 1e9;
	mx[n] = 0;
	update(n*2,s,(s+e)/2);
	update(n*2+1,(s+e)/2+1,e);
}

int get(int n,int s,int e){
	if(s > r || e < l)return -1;
	if(s == e)return min(mn[n],mx[n]);
	pro(n*2,s,e);
	pro(n*2+1,s,e);
	mn[n] = 1e9;
	mx[n] = 0;
	return max(get(n*2,s,(s+e)/2) , get(n*2+1,(s+e)/2+1,e));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<maxn;i++)mn[i] = 1e9;
	for(int i=0;i<k;i++){
		left[i]++;
		right[i]++;
		l = left[i];
		r = right[i];
		val = height[i];
		t = op[i];
		update(1,1,n);
	}
	for(int i=0;i<k;i++){
		l = r = i+1;
		height[i] = get(1,1,n);
	}
	return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 16768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 16768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 16896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 16768 KB Output isn't correct
2 Halted 0 ms 0 KB -