제출 #565074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
565074		Spade1	Gap (APIO16_gap)	C++14	0 / 100	64 ms	3436 KiB

gap

#include<bits/stdc++.h>
#include "gap.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define INF INT_MAX
using namespace std;

const int NN = 1e5 + 10;

ll mx[NN];
ll mn[NN];
pii ed[NN];

ll findGap(int T, int N) {
    ll l, r;
    MinMax(0, 1e18, &l, &r);
    ll range = r-l+1;
    ll sz = ceil(1.0*range/(N+1));
    MinMax(l+1, l+sz-1, &mn[1], &mx[1]);
    mn[1] = l;
    ed[1] = {l, l+sz-1};
    if (mx[1] == -1) mx[1] = mn[1];
    l += sz;
    for (int i = 2; i <= N; ++i) {
        MinMax(l, l+sz-1, &mn[i], &mx[i]);
        ed[i] = {l, l+sz-1};
        l += sz;
    }

    if (r-1 >= l) {
        MinMax(l, r-1, &mn[N+1], &mx[N+1]);
        mx[N+1] = r;
        if (mn[N+1] == -1) mn[N+1] = mx[N+1];
        ed[N+1] = {l, r};
    }

    ll ans = 0;
    for (int i = 2; i <= N; ++i) {
        if (mn[i] != 1) continue;
        ll cur = ed[i-1].nd - mx[i-1];
        while (mn[i] == -1) {
            i++;
            cur += sz;
        }
        cur += mn[i+1] - ed[i+1].st;
        ans = max(ans, cur);
        i--;
    }

    return ans;
}

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