Submission #1075780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075780		alexdd	Gap (APIO16_gap)	C++17	0 / 100	35 ms	1216 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;
}
long long findGap(int32_t T, int32_t N)
{
    if(N<=100)
        return 1;
    int rez=1;
    pair<int,int> tot = qry(0,INF);
    int cur=tot.first;
    while(cur+rez+1 < tot.second)
    {
        pair<int,int> aux = qry(cur+1,cur+rez);
        if(aux.first!=-1)
        {
            cur = aux.second;
            continue;
        }
        int c=rez;
        while(1)
        {
            c=c*2;
            aux = qry(cur+1,cur+c);
            if(aux.first!=-1)
            {
                rez = max(rez, aux.first - cur);
                cur = aux.second;
                break;
            }
        }
    }
    return rez;
}

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