Submission #1119333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119333		jerzyk	Distributing Candies (IOI21_candies)	C++17	3 / 100	1126 ms	28236 KiB

candies

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 2000'000'000'000'000'000LL;
const int II = 1'000'000'007;
const ll M = 1000'000'007LL;
const int N = 100'007;
int tab[N], answer[N];

ll sum[N]; int dod[N];
int que[N];
vector<int> qb[N], qe[N];

int Calc(ll x, int q)
{
    //cerr << "C: " << x << "\n";
    int pos = q;
    ll mi = I, ma = -I, mi1 = I, ma1 = -I;
    for(int i = 1; i <= q; ++i)
    {
        sum[i] = sum[i - 1] + dod[i];
        //cerr << sum[i] << " ";
    }
    //cerr << "\n";
    for(int i = q; i >= 1; --i)
    {
        mi = min(mi, sum[i]);
        ma = max(ma, sum[i]);
        if(ma - mi > x)
            break;
    }
    //cerr << mi << " " << ma << "\n";
    for(int i = q; i >= 1; --i)
    {
        mi1 = min(mi1, sum[i]);
        ma1 = max(ma1, sum[i]);
        if(ma1 != ma && mi1 != mi)
            pos = i - 1;
        else
            break;
    }
    //cerr << pos << " " << sum[pos] << "\n";
    if(ma == ma1)
        return x + (sum[q] - sum[pos]);
    return (sum[q] - sum[pos]);
}

void DoA(int n, int q)
{
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j < (int)qb[i].size(); ++j)
            dod[qb[i][j]] += que[qb[i][j]];
        for(int j = 0; j < (int)qe[i].size(); ++j)
            dod[qe[i][j]] -= que[qe[i][j]];
        answer[i] = Calc(tab[i], q);
    }
}

vector<int> distribute_candies(vector<int> _c, vector<int> _l, vector<int> _r, vector<int> _v)
{
    int n = _c.size(), q = _l.size();
    for(int i = 1; i <= n; ++i)
        tab[i] = _c[i - 1];
    que[1] = 2 * II;
    que[2] = -2 * II;
    qb[1].pb(1); qb[1].pb(2);
    for(int i = 3; i <= q + 2; ++i)
    {
        que[i] = _v[i - 3];
        qb[_l[i - 3] + 1].pb(i);
        qe[_r[i - 3] + 2].pb(i);
    }
    q += 2;
    DoA(n, q);
    vector<int> ans;
    for(int i = 1; i <= n; ++i)
        ans.pb(answer[i]);
    return ans;
}

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