Submission #609666

#	Time	Username	Problem	Language	Result	Execution time	Memory
609666		AugustinasJucas	Gap (APIO16_gap)	C++14	0 / 100	28 ms	2012 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

int n;
set<long long> setas;

void calc(int L, int R) {
    if(L > R) return ;
    long long mn, mx;
    MinMax(L, R, &mn, &mx);
    if(mn == -1) return ;

    long long mid = (L + R) / 2;
    long long MX = mx;
    long long sk = -1;
    MinMax(mid, R, &mn, &mx);
    if(mn == -1) {
        sk = MX;
        calc(L, MX-1);
    }else {
        sk = mn;
        calc(L, sk-1);
        calc(mid+1, mx-1);
        setas.insert(mx);
    }
    setas.insert(sk);



}

long long findGap(int T, int N) {
    n = N;
    long long L = 0, R = 1e18;
    calc(L, R);
    vector<long long> mas;
    for(auto x : setas) mas.push_back(x);

    long long ans = 0;
    for(int i = 0; i < n-1; i++) {
        ans = max(ans, mas[i+1] - mas[i]);
    }
    return ans;
}

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