Submission #1074861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074861		alexdd	Gap (APIO16_gap)	C++17	10.06 / 100	69 ms	2860 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
pair<int,int> qry(int le, int ri)
{
    pair<int,int> aux;
    MinMax(le,ri,&aux.first,&aux.second);
    return aux;
}
struct node
{
    int prim,ult,rez;
};
node combine(node x, node y)
{
    if(x.ult==-1)
        return y;
    if(y.ult==-1)
        return x;
    node aux;
    aux.rez = max({x.rez, y.rez, y.prim - x.ult});
    aux.prim = x.prim;
    aux.ult = y.ult;
    return aux;
}
node recursiv(int st, int dr, pair<int,int> aux)
{
    if(aux.first==-1) aux = qry(st,dr);
    if(aux.first==-1) return {-1,-1,-1};
    if(aux.first==aux.second) return {aux.first,aux.first,0};
    int mij=(st+dr)/2;
    if(aux.first > mij) return recursiv(mij+1,dr,aux);
    if(aux.second <= mij) return recursiv(st,mij,aux);
    return combine(recursiv(st,mij,{-1,-1}),recursiv(mij+1,dr,{-1,-1}));
}
long long findGap(int32_t T, int32_t N)
{
    node aux = recursiv(0,INF,{-1,-1});
    return aux.rez;
}

• Subtask 1: 0 / 30
• Subtask 2: 10.0600347014 / 70