| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 646352 | Tenis0206 | Gap (APIO16_gap) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
long long bck = 1000;
struct nod
{
long long val,Min,Max;
};
nod divide1(long long st, long long dr)
{
if(st > dr)
{
return nod{-1,-1,-1};
}
long long x,y;
MinMax(st,dr,&x,&y);
if(x==-1)
{
return nod{-1,-1,-1};
}
if(x==y)
{
return nod{-1,x,y};
}
long long mij = (x + y) >> 1;
nod l = divide1(x+1,mij);
nod r = divide1(mij+1,y-1);
long long rez = -1;
if(l.Max!=-1 && r.Min!=-1)
{
rez = max(rez,r.Min-l.Max);
}
rez = max(rez,l.val);
rez = max(rez,r.val);
long long Max = max(l.Max,r.Max);
long long Min;
if(l.Min==-1)
{
Min = r.Min;
}
else
{
Min = l.Min;
}
if(Min!=-1)
{
rez = max(rez,Min - x);
}
if(Max!=-1)
{
rez = max(rez,y - Max);
}
return nod{rez,x,y};
}
nod divide2(long long st, long long dr)
{
if(st > dr)
{
return nod{-1,-1,-1};
}
long long x,y;
MinMax(st,dr,&x,&y);
if(x==-1)
{
return nod{-1,-1,-1};
}
if(x==y)
{
return nod{-1,x,y};
}
long long last = st - 1;
long long rez = -1;
long long Max = -1;
for(int i=1;i<=bck;i++)
{
long long mij = st + ((dr - st) / bck) * i;
if(i==bck)
{
mij = dr;
}
nod son = divide2(last+1,mij);
last = mij;
rez = max(rez,son.val);
if(Max!=-1 && son.Min!=-1)
{
rez = max(rez,son.Min - Max);
}
if(son.Max!=-1)
{
Max = son.Max;
}
}
return nod{rez,x,y};
}
long long findGap(int t, int n)
{
bck = min(bck,n);
return divide2(1,1e18).val;
}