Submission #167897

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167897	2019-12-10T17:47:00 Z	muhi1112	Pismo (COCI18_pismo)	C++17	40 / 70	936 ms	40288 KB

pismo

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define f1 first
#define s2 second
#define pb push_back
#define mp make_pair
#define ll long long
#define fri(a) freopen(a,"r",stdin);
#define fro(a) freopen(a,"w",stdout);
const int N=1e5+5;
const int INF=1e9+7;

int n,dizi[N],lok[N],a,b,c,d,ans1=INF,cnt;
pair<int,int>minst[N][25],maxst[N][25];

void loki(){
	for(int i=2;i<N;i++){
		lok[i]=lok[i/2]+1;
	}
}
void build(){
	for(int j=1;j<25;j++){
		for(int i=0;i+(1<<j)<N;i++){
			minst[i][j]=min(minst[i][j-1],minst[i+(1<<(j-1))][j-1]);
			maxst[i][j]=max(maxst[i][j-1],maxst[i+(1<<(j-1))][j-1]);
		}
	}
}
pair<int,int> qmax(int l,int r){
	int j=lok[(r-l+1)];
	return max(maxst[l][j],maxst[r-(1<<j)+1][j]);
}
pair<int,int> qmin(int l,int r){
	int j=lok[(r-l+1)];
	return min(minst[l][j],minst[r-(1<<j)+1][j]);
}

int solve(int l,int r){
	cnt++;
	if(l>=r){
		return INF;
	}
	pair<int,int> mini=qmin(l,r);
	pair<int,int> maxi=qmax(l,r);
	//cout<<l<<" "<<r<<" "<<mini.s2<<" "<<maxi.s2<<endl;
	int ans=INF;
	ans=min(ans,maxi.f1-mini.f1);
	ans=min(solve(l,mini.s2-1),ans);
	ans=min(solve(mini.s2+1,r),ans);
	//ans=min(solve(l,maxi.s2-1),ans);
	ans=min(solve(maxi.s2+1,r),ans);
	ans1=min(ans,ans1);
	if(cnt>=150000000){
		cout<<ans1<<endl;
		exit(0);
	}
	return ans;
}
int main(){
	//fri("in.txt");
	//fro("out.txt");
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>dizi[i];
		minst[i][0]={dizi[i],i};
		maxst[i][0]={dizi[i],i};
	}
	loki();
	build();
	//cout<<qmax(1,2).f1<<" "<<qmax(1,2).s2<<endl;
	cout<<solve(0,n-1)<<endl;

return 0;
}

Subtask #1

40.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	39800 KB	Output is correct
2	Correct	112 ms	39800 KB	Output is correct
3	Correct	92 ms	39928 KB	Output is correct
4	Correct	86 ms	39928 KB	Output is correct
5	Incorrect	936 ms	40288 KB	Output isn't correct
6	Incorrect	918 ms	40268 KB	Output isn't correct
7	Incorrect	915 ms	40276 KB	Output isn't correct