Submission #1074858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074858		alexdd	Gap (APIO16_gap)	C++17	8.45 / 100	84 ms	2896 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 = 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;
    return combine(recursiv(st,mij),recursiv(mij+1,dr));
}
long long findGap(int32_t T, int32_t N)
{
    node aux = recursiv(0,INF);
    return aux.rez;
}

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