Codeforces Round #631 Editorial
Difference between en18 and en19, changed 53 character(s)
#### **Div.1 E is still under construction...**↵

[tutorial:1330A]↵

<spoiler summary="author's code:">↵
~~~~~↵
#include<cstdio>↵
const int MAX_V = 201;↵
bool achieve[MAX_V];↵
void solve() {↵
    int n, x;↵
    scanf("%d%d", &n, &x);↵
    for(int i = 1; i <= n + x; i++) {↵
        achieve[i] = false;↵
    }↵
    for(int i = 1; i <= n; i++) {↵
        int ranking;↵
        scanf("%d", &ranking);↵
        achieve[ranking] = true;↵
    }↵
    for(int k = n + x; k > 0; k--) {↵
        int v = 0;↵
        for(int i = 1; i <= k; i++) {↵
            if(!achieve[i]) v++;↵
        }↵
        if(v <= x) {↵
            printf("%d\n", k);↵
            return;↵
        }↵
    }↵
}↵
int main() {↵
    int T;↵
    scanf("%d", &T);↵
    while(T--) solve();↵
    return 0;↵
}↵
~~~~~↵

</spoiler>↵


[tutorial:1330B]↵



<spoiler summary="author's code">↵
~~~~~↵
#include<cstdio>↵
const int SIZE = 200000;↵
int p[SIZE];↵
int ans[SIZE][2];↵
int ans_cnt;↵
bool judge(int a[], int n){↵
    static int used[SIZE+1];↵
    for(int i = 1; i <= n; i++) used[i] = 0;↵
    for(int i = 0; i < n; i++) used[a[i]] = 1;↵
    for(int i = 1; i <= n; i++) {↵
        if(!used[i]) return 0;↵
    }↵
    return 1;↵
}↵
bool judge(int len1, int n){↵
    return judge(p, len1) && judge(p + len1, n - len1);↵
}↵
int main() {↵
    int t = 0;↵
    scanf("%d", &t);↵
    while(t--) {↵
        ans_cnt = 0;↵
        int n;↵
        scanf("%d", &n);↵
        int ma=0;↵
        for(int i = 0; i < n; i++) {↵
            scanf("%d", &p[i]);↵
            if(ma < p[i]) ma = p[i];↵
        }↵
        if(judge(n - ma,n)) {↵
            ans[ans_cnt][0] = n - ma;↵
            ans[ans_cnt++][1] = ma;↵
        }↵
        if(ma * 2 != n && judge(ma,n)) {↵
            ans[ans_cnt][0] = ma;↵
            ans[ans_cnt++][1] = n - ma;↵
        }↵
        printf("%d\n", ans_cnt);↵
        for(int i = 0; i < ans_cnt; i++) {↵
            printf("%d %d\n", ans[i][0], ans[i][1]);↵
        }↵
    }↵
    return 0;↵
}↵
~~~~~↵

</spoiler>↵

[tutorial:1329A]↵

<spoiler summary="author's code">↵
~~~~~↵
#include<bits/stdc++.h>↵
const int SIZE = 100002;↵
int len[SIZE];↵
long long suffix_sum[SIZE];↵
void err() {puts("-1");}↵
void solve() {↵
    int N, M;↵
    scanf("%d%d", &N, &M);↵
    for(int i = 1; i <= M; i++) {↵
        scanf("%d", &len[i]);↵
        if(len[i] + i - 1 > N) {↵
            err();↵
            return;↵
        }↵
    }↵
    for(int i = M; i > 0; i--) {↵
        suffix_sum[i] = suffix_sum[i + 1] + len[i];↵
    }↵
    if(suffix_sum[1] < N) {↵
        err();↵
        return;↵
    }↵
    for(int i = 1; i <= M; i++) {↵
        printf("%lld", std::max((long long)i, N - suffix_sum[i] + 1));↵
        if(i < M) putchar(' ');↵
        else puts("");↵
    }↵
}↵
int main() {↵
    solve();↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:1329B]↵

<spoiler summary="author's code">↵
~~~~~↵
#include<bits/stdc++.h>↵
void solve(){↵
    int d, m;↵
    scanf("%d%d",&d, &m);↵
    long long answer=1;↵
    for(int i = 0; i < 30; i++) {↵
        if(d < (1 << i)) break;↵
        answer = answer * (std::min((1 << (i+1)) - 1, d) - (1 << i) + 2) % m;↵
    }↵
    answer--;↵
    if(answer < 0) answer += m;↵
    printf("%lld\n",answer);↵
}↵
int main() {↵
    int T;↵
    scanf("%d", &T);↵
    while(T--) {↵
        solve();↵
    }↵
}↵
~~~~~↵

</spoiler>↵

[tutorial:1329C]↵

[a super simple solution which is differet to this blog](https://codeforces.com/blog/entry/75559?#comment-597934) provided by [user:Swistakk,2020-04-05].↵



<spoiler summary="author's code (from bottom to top with min heap)">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
const int SIZE = 1<<20;↵
int INF = 1000000001;↵
pair<int, int> a[SIZE];↵
int final_v[SIZE];↵
bool used[SIZE];↵
int h, g;↵
void pull(int id) {↵
    while(a[id] > min(a[id<<1], a[(id<<1)|1])) {↵
        if(a[id<<1] < a[(id << 1) | 1]) {↵
            swap(a[id<<1], a[id]);↵
            id <<= 1;↵
        }↵
        else {↵
            swap(a[(id<<1)|1], a[id]);↵
            id = (id << 1) | 1;↵
        }↵
        if(id >= (1 << h)) return;↵
    }↵
}↵
void solve() {↵
    scanf("%d%d", &h, &g);↵
    long long an = 0;↵
    for(int i = 1; i < (1 << h); i++) {↵
        used[i] = 0;↵
        scanf("%d", &a[i].first);↵
        a[i].second = i;↵
        final_v[i] = 0;↵
    }↵
    h--;↵
    for(int lv = h - 1; lv >= 0; lv--) {↵
        int ll = 1 << lv;↵
        int rr = 1 << (lv + 1);↵
        for(int i = ll; i < rr; i++) {↵
            pair<int, int> tmp = a[i];↵
            int bot = i << (h - lv);↵
            a[i] = a[bot];↵
            a[bot] = make_pair(INF, 0);↵
            pull(i);↵
            if(lv < g) {↵
                int need_mi = max(final_v[i * 2], final_v[i * 2 + 1]);↵
                while(a[i].first < need_mi) {↵
                    a[i] = make_pair(INF, 0);↵
                    pull(i);↵
                }↵
                an += final_v[i] = a[i].first;↵
                used[a[i].second] = 1;↵
                a[i] = tmp;↵
                pull(i);↵
            }↵
            else {↵
                a[bot] = tmp;↵
            }↵
        }↵
    }↵
    printf("%lld\n", an);↵
    bool first_time = true;↵
    for(int i = (1 << (h + 1)) - 1; i > 0; i--) {↵
        if(!used[i]) {↵
            if(!first_time) printf(" ");↵
            else first_time = false;↵
            printf("%d", i);↵
        }↵
    }↵
    puts("");↵
}↵
int main(){↵
    int T;↵
    scanf("%d", &T);↵
    while(T--) solve();↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵


<spoiler summary="isaf27's code(from bottom to top with sorted array)">↵
~~~~~↵
//#pragma GCC optimize("O3")↵
#include <bits/stdc++.h>↵

using namespace std;↵

//defines↵
typedef long long ll;↵
typedef long double ld;↵
#define TIME clock() * 1.0 / CLOCKS_PER_SEC↵
#define prev _prev↵
#define y0 _y0↵
#define kill _kill↵

//permanent constants↵
const ld pi = acos(-1.0);↵
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};↵
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};↵
const int dx[4] = {0, 1, 0, -1};↵
const int dy[4] = {1, 0, -1, 0};↵
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};↵
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};↵
const int alf = 26;↵
const int dig = 10;↵
const int two = 2;↵
const int th = 3;↵
const ll prost = 239;↵
const ll btc = 30;↵
const ld eps = 1e-8;↵
const ll INF = (ll)(1e18 + 239);↵
const int BIG = (int)(1e9 + 239);↵
const int MOD = 1e9 + 7; //↵

//random↵
mt19937 rnd(239); //(chrono::high_resolution_clock::now().time_since_epoch().count());↵

//constants↵
const int M = (int)(2e5 + 239);↵
const int N = (int)(2e3 + 239);↵
const int L = 20;↵
const int T = (1 << 20) + 239;↵
const int B = 500;↵
const int X = 35;↵
const int T2 = 2 * T;↵

int h, g, a[T2], n;↵
bool mark[T];↵
int id[T], buf[T], timer;↵

bool cmp(int i, int j)↵
{↵
    return (a[i] < a[j]);↵
}↵

int pos;↵

void dfs_write(int p)↵
{↵
    id[pos++] = p;↵
    if (2 * p + 1 <= n)↵
    {↵
        dfs_write(2 * p);↵
        dfs_write(2 * p + 1);↵
    }↵
}↵

int dfs(int p, int sz)↵
{↵
    if ((1 << (g - 1)) <= p && p < (1 << g))↵
    {↵
        int l = timer;↵
        timer += sz;↵
        pos = l;↵
        dfs_write(p);↵
        sort(id + l, id + l + sz, cmp);↵
        mark[id[l]] = true;↵
        return id[l];↵
    }↵
    int l = timer;↵
    int new_sz = ((sz - 1) / 2);↵
    int s1 = dfs(2 * p, new_sz);↵
    int s2 = dfs(2 * p + 1, new_sz);↵
    merge(id + l, id + l + new_sz, id + l + new_sz, id + l + new_sz + new_sz, buf, cmp);↵
    buf[sz - 1] = p;↵
    for (int i = 0; i < sz; i++)↵
        id[i + l] = buf[i];↵
    timer++;↵
    if (cmp(s1, s2))↵
        s1 = s2;↵
    for (int i = 0; i < sz; i++)↵
        if (cmp(s1, id[i + l]))↵
        {↵
            mark[id[i + l]] = true;↵
            return id[i + l];↵
        }↵
    return 0;↵
}↵

void rm(int i)↵
{↵
    if (a[2 * i] == 0 && a[2 * i + 1] == 0)↵
    {↵
        a[i] = 0;↵
        mark[i] = false;↵
        return;↵
    }↵
    if (a[2 * i] > a[2 * i + 1])↵
    {↵
        a[i] = a[2 * i];↵
        mark[i] = mark[2 * i];↵
        rm(2 * i);↵
    }↵
    else↵
    {↵
        a[i] = a[2 * i + 1];↵
        mark[i] = mark[2 * i + 1];↵
        rm(2 * i + 1);↵
    }↵
}↵

void dfs_ans(int p)↵
{↵
    while (a[p] != 0 && !mark[p])↵
    {↵
        cout << p << " ";↵
        rm(p);↵
    }↵
    if (a[p] == 0)↵
        return;↵
    dfs_ans(2 * p);↵
    dfs_ans(2 * p + 1);↵
}↵

void solve()↵
{↵
    cin >> h >> g;↵
    n = (1 << h) - 1;↵
    for (int i = 1; i <= n; i++)↵
        cin >> a[i];↵
    for (int i = 1; i <= n; i++)↵
        mark[i] = false;↵
    timer = 0;↵
    dfs(1, n);↵
    ll ans = 0;↵
    for (int i = 1; i <= n; i++)↵
        if (mark[i])↵
            ans += a[i];↵
    cout << ans << "\n";↵
    dfs_ans(1);↵
    cout << "\n";↵
    for (int i = 0; i <= n; i++)↵
        a[i] = 0;↵
}↵

int32_t main()↵
{↵
#ifdef ONPC↵
    freopen("input", "r", stdin);↵
#endif↵
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
    int t;↵
    cin >> t;↵
    while (t--)↵
        solve();↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵

<spoiler summary="author's code (from top to bottom)">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
const int SIZE = 1<<20;↵
int INF = 1000000001;↵
int a[SIZE], ops[SIZE];↵
int h, g;↵
int qq[24], qn;↵
int pull(int id) {↵
    int tmp = a[id];↵
    a[id] = 0;↵
    qn = 0;↵
    qq[qn++] = id;↵
    while(id * 2 < (1 << h) && a[id] < max(a[id<<1], a[(id<<1)|1])) {↵
        if(a[id<<1] > a[(id << 1) | 1]) {↵
            swap(a[id<<1], a[id]);↵
            id <<= 1;↵
        }↵
        else {↵
            swap(a[(id<<1)|1], a[id]);↵
            id = (id << 1) | 1;↵
        }↵
        qq[qn++] = id;↵
    }↵
    if(id < (1 << g)) {↵
        for(int i = qn - 1; i > 0; i--) {↵
            a[qq[i]] = a[qq[i - 1]];↵
        }↵
        a[qq[0]] = tmp;↵
        return 0;↵
    }↵
    return tmp;↵
}↵
void solve() {↵
    scanf("%d%d", &h, &g);↵
    long long an = 0;↵
    for(int i = 1; i < (1 << h); i++) {↵
        scanf("%d", &a[i]);↵
        an += a[i];↵
    }↵
    int need = 0;↵
    for(int i = 1; i < (1 << g); i++) {↵
        while(1) {↵
            int v = pull(i);↵
            if(v) {↵
                an -= v;↵
                ops[need++] = i;↵
            }↵
            else break;↵
        }↵
    }↵
    printf("%lld\n", an);↵
    for(int i = 0; i < need; i++) printf("%d%c", ops[i], " \n"[i == need - 1]);↵
}↵
int main(){↵
    int T;↵
    scanf("%d", &T);↵
    while(T--) solve();↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵

[tutorial:1329D]↵


<spoiler summary="author's code">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
const int SIZE = 2e5+10;↵
char s[SIZE];↵
int cnt[SIZE];↵
int cc[26];↵
int all_cnt;↵
int ma;↵
void update_ma() {↵
    while(ma > 0 && !cnt[ma]) ma--;↵
}↵
void dec1(int id) {↵
    cnt[cc[id]]--;↵
    cc[id]--;↵
    cnt[cc[id]]++;↵
}↵
pair<int, int> stk[SIZE];↵
int sn;↵
int m;↵
int now;↵
int last_len;↵
void add(int i, bool flag) {↵
    if(flag) {↵
        dec1(stk[sn - 1].second);↵
        dec1(stk[i].second);↵
        all_cnt -= 2;↵
        printf("%d %d\n",now + 1, now + stk[i].first);↵
        update_ma();↵
        sn--;↵
        now -= stk[sn].first;↵
        if(i + 1 < m) {↵
            stk[i + 1].first += stk[sn].first;↵
        }↵
        else{↵
            last_len += stk[sn].first;↵
        }↵
    }↵
    else {↵
        stk[sn++] = stk[i];↵
        now += stk[i].first;↵
    }↵
}↵
void solve(){↵
    scanf("%s", s);↵
    int n = strlen(s);↵
    all_cnt = 0;↵
    int lt = 0;↵
    m = 0;↵
    for(int i = 1; i < n; i++) {↵
        if(s[i] == s[i - 1]) {↵
            cc[s[i] - 'a']++;↵
            all_cnt++;↵
            stk[m++] = make_pair(i - lt, (int)(s[i] - 'a'));↵
            lt = i;↵
        }↵
    }↵
    last_len = n - lt;↵
    ma = 0;↵
    for(int i = 0; i < 26; i++) {↵
        cnt[cc[i]]++;↵
        ma = max(ma, cc[i]);↵
    }↵
    printf("%d\n", 1 + max(ma, (all_cnt + 1) / 2));↵
    if(ma * 2 < all_cnt) {↵
        sn = now = 0;↵
        for(int i = 0; i < m; i++) {↵
            add(i, sn && stk[sn - 1].second != stk[i].second && ma * 2 < all_cnt);↵
        }↵
        m = sn;↵
    }↵
    int main_id = -1;↵
    for(int i = 0; i < 26; i++) {↵
        if(cc[i] == ma) main_id = i;↵
    }↵
    sn = now = 0;↵
    for(int i = 0; i < m; i++) {↵
        add(i, sn && ((stk[sn - 1].second == main_id) ^ (stk[i].second == main_id)));↵
    }↵
    for(int i = 0; i < sn; i++) {↵
        printf("%d %d\n",1 ,stk[i].first);↵
    }↵
    printf("%d %d\n", 1, last_len);↵
    memset(cc, 0, sizeof(cc));↵
    memset(cnt, 0, sizeof(int) * (ma + 1));↵
}↵
int main(){↵
    int T;↵
    scanf("%d", &T);↵
    for(int i = 1; i <= T; i++) solve();↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵


[tutorial:1329E]↵

<spoiler summary="isaf27's solution">↵

~~~~~↵
//#pragma GCC optimize("O3")↵
#include <bits/stdc++.h>↵

using namespace std;↵

//defines↵
typedef long long ll;↵
typedef long double ld;↵
#define TIME clock() * 1.0 / CLOCKS_PER_SEC↵
#define prev _prev↵
#define y0 _y0↵
#define kill _kill↵

//permanent constants↵
const ld pi = acos(-1.0);↵
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};↵
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};↵
const int dx[4] = {0, 1, 0, -1};↵
const int dy[4] = {1, 0, -1, 0};↵
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};↵
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};↵
const int alf = 26;↵
const int dig = 10;↵
const int two = 2;↵
const int th = 3;↵
const ll prost = 239;↵
const ll btc = 30;↵
const ld eps = 1e-8;↵
const ll INF = (ll)(1e18 + 239);↵
const int BIG = (int)(1e9 + 239);↵
const int MOD = 1e9 + 7; //↵

//random↵
mt19937 rnd(239); //(chrono::high_resolution_clock::now().time_since_epoch().count());↵

//constants↵
const int M = (int)(4e5 + 239);↵
const int N = (int)(2e3 + 239);↵
const int L = 20;↵
const int T = (1 << 18) + 239;↵
const int B = 500;↵
const int X = 210;↵

ll up(ll a, ll b)↵
{↵
    return (a + b - 1) / b;↵
}↵

ll down(ll a, ll b)↵
{↵
    return a / b;↵
}↵

int m;↵
ll l[M], n, k;↵

void solve()↵
{↵
    cin >> n >> m >> k;↵
    ll pr = 0;↵
    for (int i = 0; i < m; i++)↵
    {↵
        ll p;↵
        cin >> p;↵
        l[i] = p - pr;↵
        pr = p;↵
    }↵
    l[m++] = n - pr;↵
    //for (int i = 0; i < m; i++)↵
    //    cerr << l[i] << " ";↵
    //cerr << "\n";↵
    ll sum = k + m;↵
    ll bl = 1;↵
    ll br = n + 1;↵
    while (br - bl > 1)↵
    {↵
        ll h = (bl + br) >> 1LL;↵
        ll cur = 0;↵
        for (int i = 0; i < m; i++)↵
            cur += down(l[i], h);↵
        if (sum <= cur)↵
            bl = h;↵
        else↵
            br = h;↵
    }↵
    ll MIN = bl;↵
    bl = 0;↵
    br = n + 1;↵
    while (br - bl > 1)↵
    {↵
        ll h = (bl + br) >> 1LL;↵
        ll cur = 0;↵
        for (int i = 0; i < m; i++)↵
            cur += up(l[i], h);↵
        if (sum >= cur)↵
            br = h;↵
        else↵
            bl = h;↵
    }↵
    ll MAX = br;↵
    vector<pair<ll, ll>> ban;↵
    for (int i = 0; i < m; i++)↵
    {↵
        if (up(l[i], MAX) <= down(l[i], MIN))↵
            continue;↵
        ll bl = 0;↵
        ll br = MIN;↵
        while (br - bl > 1)↵
        {↵
            ll h = (bl + br) >> 1LL;↵
            if (down(l[i], h) == down(l[i], MIN))↵
                br = h;↵
            else↵
                bl = h;↵
        }↵
        ll first = MIN - br;↵
        bl = MAX;↵
        br = INF;↵
        while (br - bl > 1)↵
        {↵
            ll h = (bl + br) >> 1LL;↵
            if (up(l[i], MAX) == up(l[i], h))↵
                bl = h;↵
            else↵
                br = h;↵
        }↵
        ll second = bl - MAX;↵
        ban.push_back(make_pair(first, second));↵
    }↵
    ll add = MAX - MIN;↵
    if (ban.empty())↵
    {↵
        cout << add << "\n";↵
        return;↵
    }↵
    sort(ban.begin(), ban.end());↵
    vector<pair<ll, ll>> a;↵
    for (int i = 0; i < (int)ban.size(); i++)↵
    {↵
        while (!a.empty() && a.back().second <= ban[i].second)↵
            a.pop_back();↵
        a.push_back(ban[i]);↵
    }↵
    ll ans = INF;↵
    ans = min(a[0].second + 1, ans);↵
    ans = min(a.back().first + 1, ans);↵
    for (int i = 0; i + 1 < (int)a.size(); i++)↵
        ans = min(ans, a[i].first + a[i + 1].second + 2);↵
    cout << ans + add << "\n";↵
}↵

int32_t main()↵
{↵
#ifdef ONPC↵
    freopen("input", "r", stdin);↵
#endif↵
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
    int t;↵
    cin >> t;↵
    while (t--)↵
        solve();↵
    return 0;↵
}↵

~~~~~↵
</spoiler>↵

<spoiler summary="author's solution">↵

~~~~~↵
/*{{{*/↵
#include<cstdio>↵
#include<cstdlib>↵
#include<cstring>↵
#include<cmath>↵
#include<algorithm>↵
#include<string>↵
#include<iostream>↵
#include<sstream>↵
#include<set>↵
#include<map>↵
#include<queue>↵
#include<bitset>↵
#include<vector>↵
#include<limits.h>↵
#include<assert.h>↵
#define SZ(X) ((int)(X).size())↵
#define ALL(X) (X).begin(), (X).end()↵
#define REP(I, N) for (int I = 0; I < (N); ++I)↵
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)↵
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)↵
#define FORS(I, S) for (int I = 0; S[I]; ++I)↵
#define RS(X) scanf("%s", (X))↵
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))↵
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())↵
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)↵
#define MP make_pair↵
#define PB push_back↵
#define MS0(X) memset((X), 0, sizeof((X)))↵
#define MS1(X) memset((X), -1, sizeof((X)))↵
#define LEN(X) strlen(X)↵
#define F first↵
#define S second↵
using namespace std;↵
typedef long long LL;↵
typedef unsigned long long ULL;↵
typedef long double LD;↵
typedef pair<int,int> PII;↵
typedef vector<int> VI;↵
typedef vector<LL> VL;↵
typedef vector<PII> VPII;↵
typedef pair<LL,LL> PLL;↵
typedef vector<PLL> VPLL;↵
template<class T> void _R(T &x) { cin >> x; }↵
void _R(int &x) { scanf("%d", &x); }↵
void _R(LL &x) { scanf("%lld", &x); }↵
void _R(double &x) { scanf("%lf", &x); }↵
void _R(char &x) { scanf(" %c", &x); }↵
void _R(char *x) { scanf("%s", x); }↵
void R() {}↵
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }↵
template<class T> void _W(const T &x) { cout << x; }↵
void _W(const int &x) { printf("%d", x); }↵
void _W(const LL &x) { printf("%lld", x); }↵
void _W(const double &x) { printf("%.16f", x); }↵
void _W(const char &x) { putchar(x); }↵
void _W(const char *x) { printf("%s", x); }↵
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}↵
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }↵
void W() {}↵
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }↵
#ifdef HOME↵
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}↵
#else↵
 #define DEBUG(...)↵
#endif↵
int MOD = 1e9+7;↵
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}↵
/*}}}*/↵
const int SIZE = 1e6+10;↵
LL a[SIZE],num[SIZE];↵
bool done[SIZE],be_added[SIZE];↵
int n;↵
LL K;↵
LL get_upper_bound(int i){↵
    LL v=a[i]/num[i];↵
    if(v*num[i]!=a[i])v++;↵
    return v;↵
}↵
LL get_next_upper_bound(int i){↵
    LL v=a[i]/(num[i]-1);↵
    if(v*(num[i]-1)!=a[i])v++;↵
    return v;↵
}↵
LL go(){↵
    if(K==n){↵
        return a[n-1]-a[0];↵
    }↵
    LL ll=1,rr=a[n-1];↵
    while(ll<rr){↵
        LL mm=(ll+rr)/2;↵
        LL need=0;↵
        REP(i,n){↵
            if(a[i]>mm)need+=a[i]/mm;↵
            else need++;↵
        }↵
        if(need>=K)ll=mm+1;↵
        else rr=mm;↵
    }↵
    LL low=ll;↵
    VPLL pp;↵
    LL need=0;↵
    REP(i,n){↵
        if(a[i]>=low){↵
            num[i]=a[i]/low;↵
            pp.PB({a[i]/(num[i]+1),i});↵
        }↵
        else {↵
            num[i]=1;↵
        }↵
        need+=num[i];↵
    }↵
    {↵
        bool fail=0;↵
        REP(i,n){↵
            if(get_upper_bound(i)>=low){↵
                fail=1;↵
                break;↵
            }↵
        }↵
        if(!fail) return low-1-min(low-1,a[0]);↵
    }↵
    REP(i,n){↵
        if(a[i]>=low&&a[i]/(num[i]+1)==low-1){↵
            LL v=a[i]/(low-1);↵
            LL mi=min(v-num[i],K-need);↵
            num[i]+=mi;↵
            need+=mi;↵
            if(need==K)break;↵
        }↵
    }↵
    priority_queue<PLL,VPLL,greater<PLL>>added;↵
    priority_queue<PLL>top;↵
    LL mi=a[0];↵
    REP(i,n){↵
        if(num[i]>1){↵
            added.push(MP(get_next_upper_bound(i),i));↵
        }↵
        top.push(MP(get_upper_bound(i),i));↵
        mi=min(mi,a[i]/num[i]);↵
    }↵
    LL an=top.top().F-mi;↵
    REP(i,n)be_added[i]=done[i]=0;↵
    LL ma=low-1;↵
    while(!top.empty()&&!added.empty()){↵
        int id=top.top().S;↵
        if(be_added[id])break;↵
        done[id]=1;↵
        top.pop();↵
        num[id]++;↵
        mi=min(mi,a[id]/num[id]);↵
        auto tmp=added.top();↵
        added.pop();↵
        if(done[tmp.S])break;↵
        be_added[tmp.S]=1;↵
        num[tmp.S]--;↵
        if(num[tmp.S]>1)added.push({get_next_upper_bound(tmp.S),tmp.S});↵
        ma=max(ma,tmp.F);↵
        an=min(an,(top.empty()?ma:max(ma,top.top().F))-mi);↵
    }↵
    return an;↵
}↵
void solve(){↵
    LL L;↵
    //R(n,K,L);↵
    R(L,n,K);↵
    K+=n+1;↵
    LL lt=0;↵
    REP(i,n){↵
        LL x;↵
        R(x);↵
        a[i]=x-lt;↵
        lt=x;↵
    }↵
    a[n++]=L-lt;↵
    sort(a,a+n);↵
    W(go());↵
}↵
int main(){↵
    CASET{↵
        solve();↵
    }↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en21 English dreamoon_love_AA 2020-04-05 21:15:08 1 Tiny change: '5] provide proof for' -> '5] provides proof for'
en20 English dreamoon_love_AA 2020-04-05 21:14:23 143
en19 English dreamoon_love_AA 2020-04-05 20:31:48 53 Tiny change: '#### **Div.1 E is still under construction...**\n\n[tutorial:' -> '[tutorial:'
en18 English dreamoon_love_AA 2020-04-05 17:13:21 8807
en17 English dreamoon_love_AA 2020-04-05 07:59:53 159 Tiny change: 'takk].\n\n<spoil' -> 'takk].\n\n\n\n<spoil'
en16 English dreamoon_love_AA 2020-04-05 01:12:06 2 Tiny change: '# **Div.1 C E is stil' -> '# **Div.1 E is stil'
en15 English dreamoon_love_AA 2020-04-05 00:46:24 13
en14 English dreamoon_love_AA 2020-04-04 22:23:28 1518
en13 English dreamoon_love_AA 2020-04-04 22:16:37 3500
en12 English dreamoon_love_AA 2020-04-04 00:10:34 4
en11 English dreamoon_love_AA 2020-04-04 00:09:37 9 (published)
en10 English dreamoon_love_AA 2020-04-04 00:05:13 20 Tiny change: 'oiler>\n\n' -> 'oiler>\n\n\n[tutorial:1329E]\n'
en9 English dreamoon_love_AA 2020-04-04 00:04:54 18 Tiny change: 'oiler>\n\n[tutorial:1329E]\n' -> 'oiler>\n\n' (saved to drafts)
en8 English dreamoon_love_AA 2020-04-03 22:16:10 144
en7 English dreamoon_love_AA 2020-04-03 22:13:29 8 Tiny change: 'long)i, N &mdash; suffix_su' -> 'long)i, N - suffix_su'
en6 English dreamoon_love_AA 2020-04-03 21:56:32 238
en5 English dreamoon_love_AA 2020-04-03 21:44:17 5 Tiny change: '1 C and E is still und' -> '1 C and E are still und' (published)
en4 English dreamoon_love_AA 2020-04-03 21:43:34 12
en3 English dreamoon_love_AA 2020-04-03 21:42:38 7309
en2 English dreamoon_love_AA 2020-04-03 21:35:25 156
en1 English dreamoon_love_AA 2020-04-03 21:34:20 307 Initial revision (saved to drafts)