Submission #1174714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174714		gyg	Distributing Candies (IOI21_candies)	C++20	29 / 100	82 ms	14016 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array 
#define vec vector 
const int N = 2e5 + 5, Q = 2e5 + 5, INF = 1e18;

int q;
arr<int, Q> qry;
int n;
arr<int, N> hg;

arr<int, N> mn, mx;
void prp_cmp() {
    mn[n + 1] = INF, mx[n + 1] = -INF;
    for (int i = n; i >= 1; i--) {
        mn[i] = min(mn[i + 1], hg[i]);
        mx[i] = max(mx[i + 1], hg[i]);
    }
}

int srch(int x) {
    int lw = 1, hg = n;
    while (lw < hg) {
        int md = (lw + hg + 1) / 2;
        if (mx[md] - mn[md] >= x) lw = md;
        else hg = md - 1;
    }
    return (mx[lw] - mn[lw] >= x) ? lw : -1;
}
int slv(int x) {
    int i = srch(x);
    if (i == -1) return hg[n];
    if (hg[i] == mn[i]) return x - (mx[i] - hg[n]);
    else return (hg[n] - mn[i]);
}

vec<sig> distribute_candies(vec<sig> _qry, vec<sig> _l, vec<sig> _r, vec<sig> _x) {
    q = _qry.size();
    for (int i = 1; i <= q; i++) qry[i] = _qry[i - 1];
    n = _x.size() + 2;
    hg[1] = INF, hg[2] = 0;
    for (int i = 3; i <= n; i++) hg[i] = hg[i - 1] + _x[i - 3];

    prp_cmp();

    vec<sig> ans;
    for (int i = 1; i <= q; i++) 
        ans.push_back(slv(qry[i]));
    return ans;
}

/*

for (int i = 1; i <= n; i++) 
    cout << hg[i] << " ";
cout << '\n';


*/

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33