oj.uz

Submission #138181

# Submission time Handle Problem Language Result Execution time Memory
138181 2019-07-29T14:16:14 Z junodeveloper Wall (IOI14_wall) C++14
0 / 100
 203 ms 13952 KB 
#include "wall.h"
#include <algorithm>
using namespace std;
struct node {
	int mx,mn;
} T[4*100010];
void apply(int h,int mn,int mx) {
	if(T[h].mx<mn) T[h].mx=T[h].mn=mn;
	else if(mx<T[h].mn) T[h].mx=T[h].mn=mx;
	else {
		T[h].mn=max(T[h].mn,mn);
		T[h].mx=min(T[h].mx,mx);
	}
}
void update(int h,int tl,int tr,int l,int r,int mn,int mx) {
	if(tr<l||r<tl)return;
	if(h>1)apply(h,T[h/2].mn,T[h/2].mx);
	if(l<=tl&&tr<=r) {
		apply(h,mn,mx);
		return;
	}
	int mid=(tl+tr)>>1;
	update(h*2,tl,mid,l,r,mn,mx);
	update(h*2+1,mid+1,tr,l,r,mn,mx);
	T[h].mn=min(T[h*2].mn,T[h*2+1].mn);
	T[h].mx=max(T[h*2].mx,T[h*2+1].mx);
}
int query(int h,int tl,int tr,int p){
	if(h>1)apply(h,T[h/2].mn,T[h/2].mx);
	if(tl==tr) return T[h].mn;
	int mid=(tl+tr)>>1;
	if(p<=mid) return query(h*2,tl,mid,p);
	return query(h*2+1,mid+1,tr,p);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	int i,mn,mx;
	for(i=0;i<=4*n;i++) T[i]={0,0};
	for(i=0;i<k;i++) {
		if(op[i]==1) mn=height[i],mx=1e9;
		else mn=0,mx=height[i];
		update(1,0,n-1,left[i],right[i],mn,mx);
	}
	for(i=0;i<n;i++) {
		finalHeight[i]=query(1,0,n-1,i);
	}
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 183 ms 13952 KB Output is correct
3 Incorrect 203 ms 8068 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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