Submission #436819

#	Time	Username	Problem	Language	Result	Execution time	Memory
436819		edenooo	Distributing Candies (IOI21_candies)	C++17	100 / 100	687 ms	31552 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;

#define INF 1234567890
#define ll long long

ll last = 0;
pair<ll, ll> seg[530000];
ll lazy[530000];
pair<ll, ll> Merge(pair<ll, ll> l, pair<ll, ll> r)
{
    return {min(l.first,r.first), max(l.second, r.second)};
}
void Propagate(int n, int l, int r) // add
{
    if (lazy[n])
    {
        if (l != r)
        {
            lazy[n<<1] += lazy[n];
            lazy[n<<1|1] += lazy[n];
        }
        seg[n].first += lazy[n];
        seg[n].second += lazy[n];
        lazy[n] = 0;
    }
}
pair<ll, ll> Update(int L, int R, ll val, int n, int l, int r)
{
    Propagate(n, l, r);
    if (r < L || R < l) return seg[n];
    if (L <= l && r <= R)
    {
        lazy[n] += val; // add
        Propagate(n, l, r);
        return seg[n];
    }
    int mid = l+r>>1;
    return seg[n] = Merge(Update(L, R, val, n<<1, l, mid), Update(L, R, val, n<<1|1, mid+1, r));
}
ll Kth(ll C, ll mn, ll mx, int n, int l, int r) // 1 <= k <= propagated_seg[1]
{
    Propagate(n, l, r); //
    if (l == r)
    {
        mn = min(mn, seg[n].first);
        mx = max(mx, seg[n].second);
        assert(mx - mn >= C);
        if (mn == seg[n].first) return C - (mx - last);
        else return last - mn;
    }
    int mid = l+r>>1;
    Propagate(n<<1|1, mid+1, r);
    ll next_mn = min(mn, seg[n<<1|1].first), next_mx = max(mx, seg[n<<1|1].second);
    if (next_mx - next_mn >= C) return Kth(C, mn, mx, n<<1|1, mid+1, r);
    return Kth(C, next_mn, next_mx, n<<1, l, mid);
}

int N, Q;
vector<pair<int, int> > D[200201];

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    N = C.size(); Q = L.size();
    // INF와 0을 맨 앞에 끼워넣어서 예외 처리
    D[0].push_back({0, INF});
    D[0].push_back({1, -INF});
    for(int i=0; i<Q; i++)
    {
        D[L[i]].push_back({i+2, V[i]});
        D[R[i]+1].push_back({i+2, -V[i]});
    }

    vector<int> res(N);
    for(int i=0; i<N; i++)
    {
        for(auto [idx,val] : D[i])
        {
            last += val;
            Update(idx, Q+1, val, 1, 0, Q+1); //
        }
        res[i] = Kth(C[i], (ll)1e18, (ll)-1e18, 1, 0, Q+1);
    }
    return res;
}

// int main() {}

Compilation message (stderr)

candies.cpp: In function 'std::pair<long long int, long long int> Update(int, int, long long int, int, int, int)':
candies.cpp:40:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = l+r>>1;
      |               ~^~
candies.cpp: In function 'long long int Kth(long long int, long long int, long long int, int, int, int)':
candies.cpp:54:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     int mid = l+r>>1;
      |               ~^~

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