Submission #94882

#	Time	Username	Problem	Language	Result	Execution time	Memory
94882		karlopuh	Pismo (COCI18_pismo)	C++14	0 / 70	1077 ms	2424 KiB

pismo

#include <bits/stdc++.h>
using namespace std;

pair <int,int> stablo [300000];
int n;
int pot=1;
int mini = 1e9 + 10;
int pom[2];


int query(int cvor,int od,int doo,int a,int b){
	if(od<=a && doo>=b)return cvor;
	
	int rj1=-1,rj2=-1;
	if((doo+od)/2>=a){
		rj1=query(cvor*2,od,(doo+od)/2,a,b);
	}
	if((doo+od)/2+1<=b){
		rj2=query(cvor*2+1,(doo+od)/2+1,doo,a,b);
	}
	
	if(rj1==-1)return rj2;
	else if(rj2==-1) return rj1;
	else{
		pom[0]=rj1;
		pom[1]=rj2;
		return -1;
	}
}


void create(){
	for(int i=pot-1;i>=1;i--){
		stablo[i].first=min(stablo[i*2].first,stablo[i*2+1].first);
		stablo[i].second=max(stablo[i*2].second,stablo[i*2+1].second);
	}
}


int main(){
	cin>>n;
	for(;pot<=n;pot*=2);
	
	for(int i=0;i<n;i++){
		cin>>stablo[pot+i].first;
		stablo[pot+i].second=stablo[pot+i].first;
	}
	
	for(int i=pot+n;i<=pot*2-1;i++){
		stablo[i].first=1e9+10;
		stablo[i].second=-1e9+10;
	}
	
	create();
	
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			int pov=query(1,0,pot,i,j);
			if(pov==-1){
				int test=max(stablo[pom[0]].second,stablo[pom[1]].second)-min(stablo[pom[0]].first,stablo[pom[1]].first);
				if(test<mini)mini=test;
			}else{
				int test=stablo[pov].second-stablo[pov].first;
				if(test<mini)mini=test;
			}
		}
	}
	
	cout<<mini;
	
}

• Subtask 1: 0 / 70