제출 #442270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442270		blue	Distributing Candies (IOI21_candies)	C++17	0 / 100	1264 ms	53452 KiB

candies

#include "candies.h"
#include <vector>
#include <iostream>
using namespace std;

const long long INF = 3'000'000'000;

struct segtree //min, max, range add
{
    int l;
    int r;

    long long mn = 0;
    long long mx = 0;
    long long lp = 0;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        if(l == r) return;
        int m = (l+r+10)/2 - 5;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    long long rangemin(int L, int R)
    {
        if(R < l || r < L) return INF;
        else if(L <= l && r <= R) return mn;
        else return min(left->rangemin(L, R), right->rangemin(L, R));
    }

    long long rangemax(int L, int R)
    {
        if(R < l || r < L) return -INF;
        else if(L <= l && r <= R) return mx;
        else return max(left->rangemax(L, R), right->rangemax(L, R));
    }

    void add(int L, int R, long long V)
    {
        if(R < l || r < L) return;
        else if(L <= l && r <= R)
        {
            mn += V;
            mx += V;
            lp += V;
        }
        else
        {
            left->add(L, R, V);
            right->add(L, R, V);
            mn = lp + min(left->mn, right->mn);
            mx = lp + max(left->mx, right->mx);
        }
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    int N = c.size();
    int Q = l.size();

    segtree S(-1, Q);

    vector<int> insertions[N], removals[N];
    for(int i = 0; i < Q; i++)
    {
        insertions[ l[i] ].push_back(i);
        removals[ r[i] ].push_back(i);
    }

    vector<int> res(N, 0);
    long long curr_upd_sum = 0;

    for(int i = 0; i < N; i++)
    {
        for(int o: insertions[i])
        {
            S.add(o, Q, v[o]);
            curr_upd_sum += v[o];
        }

        int X = Q;
        for(int bit = 19; bit >= 0; bit--)
        {
            int X1 = X - (1 << bit);
            if(X1 < 0) continue;
            if(S.rangemax(X1, Q) - S.rangemin(X1, Q) <= c[i])
                X = X1;
        }

        long long bounds;

        // cerr << "X = " << X << '\n';

        if(S.rangemin(X-1, Q) < S.rangemin(X, Q))
            bounds = S.rangemax(X, Q) - c[i];
        else
        {
            // cerr << "entered\n";
            bounds = S.rangemin(X, Q);
        }

        // cerr << curr_upd_sum << ' ' << bounds << '\n';

        res[i] = (curr_upd_sum - bounds);

        for(int o: removals[i])
        {
            S.add(o, Q, -v[o]);
            curr_upd_sum -= v[o];
        }
    }

    return res;
}

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