Submission #443983

#	Time	Username	Problem	Language	Result	Execution time	Memory
443983		hiliy	Distributing Candies (IOI21_candies)	C++17	0 / 100	274 ms	164120 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> merge(vector<ll> v1, vector<ll> v2)
{
    vector<ll> ans(5);
    ans[0] = v1[0] + v2[0];
    if(v1[1] < v2[1] + v1[0])
        ans[1] = v1[1], ans[2] = v1[2];
    else
        ans[1] = v2[1] + v1[0], ans[2] = v2[2];
    if(v1[3] > v2[3] + v1[0])
        ans[3] = v1[3], ans[4] = v1[4];
    else
        ans[3] = v2[3] + v1[0], ans[4] = v2[4];
    return ans;
}
struct segtree{
    int sz;
    vector<int> val;
    vector<int> active;
    vector<vector<ll>> data;
    //sum - data[0]
    //minpref - data[1]
    //minind - data[2]
    //maxpref - data[3]
    //maxind - data[4]
    segtree(vector<int> v)
    {
        val = v;
        int sz = val.size() * 4 + 2;
        active.resize(sz);
        data.resize(sz, vector<ll>(5));
    }
    void change(int v, int l, int r, int pos)
    {
        if(l > pos || r < pos)
            return;
        if(l == r)
        {
            active[v] = !active[v];
            if(active[v])
            {
                data[v][0] = data[v][1] = data[v][3] = val[l];
                data[v][2] = l;
                data[v][4] = l;
            }
            else
                data[v] = vector<ll>(5);
            return;
        }
        change(v*2, l, (l + r) / 2, pos), change(v*2 + 1, (l + r) / 2 + 1, r, pos);
        if(active[v * 2])
        {
            active[v] = 1;
            if(active[v * 2 + 1])
                data[v] = merge(data[v*2], data[v*2 + 1]);
            else
                data[v] = data[v*2];
        }
        else if(active[v*2 + 1])
            data[v] = data[v*2 + 1], active[v] = 1;
    }
    pair<int, bool> getans(int v, int l, int r, int needmin, int needmax, vector<ll> d)
    {
        if(!active[v] || (data[v][1] > needmin && data[v][3] < needmax))
            return {-1, 0};
        if(l == r)
        {
            if(d[0] == -1e18)
                d = data[v];
            else
                d = merge(data[v], d);
            if(d[1] <= needmin)
                return {l, 0};
            else
                return {l, 1};
        }
        vector<ll> c;
        if(d[0] == -1e18)
            c = data[v * 2 + 1];
        else
            c = merge(data[v * 2 + 1], d);
        if(active[v * 2 + 1] && (c[1] <= needmin || c[3] >= needmax))
            return getans(v*2 + 1, (l + r) / 2 + 1, r, needmin, needmax, d);
        return getans(v * 2, l, (l + r) / 2, needmin, needmax, c);
    }
    void getinfo(int v, int l, int r, int l1, int r1, vector<ll> &d)
    {
        if(l > r1 || l1 > r || !active[v])
            return;
        if(l1 <= l && r <= r1)
        {
            if(d[0] == -1e18)
                d = data[v];
            else
                d = merge(d, data[v]);
        }
        getinfo(v*2, l, (l + r) / 2, l1, r1, d), getinfo(v*2 + 1, (l + r) / 2 + 1, r, l1, r1, d);
    }
};
vector<ll> info(segtree &t, int l, int r, int m)
{
    vector<ll> d(5);
    d[0] = -1e18;
    r = min(r, m);
    if(l <= r)
        t.getinfo(1, 0, m, l, r, d);
    if(d[0] == -1e18)
        d[0] = 0;
    return d;
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    int n = c.size(), m = l.size();
    vector<vector<int>> in(n + 1);
    reverse(v.begin(), v.end());
    reverse(l.begin(), l.end());
    reverse(r.begin(), r.end());
    v.push_back(0);
    l.push_back(0);
    r.push_back(n - 1);
    reverse(v.begin(), v.end());
    reverse(l.begin(), l.end());
    reverse(r.begin(), r.end());
    m++;
    for(int i = 0; i < m; i++)
    {
        in[l[i]].push_back(i);
        in[r[i] + 1].push_back(i);
    }
    vector<int> ans(n);
    segtree t(v);
    for(int i = 0; i < n; i++)
    {
        for(auto j : in[i])
            t.change(1, 0, m - 1, j);
        vector<ll> d(5);
        d[0] = -1e18;
        auto p = t.getans(1, 0, m - 1, -c[i], c[i], d);
        if(p.first == -1)
        {
            ans[i] = info(t, t.data[1][2] + 1, m - 1, m - 1)[0];
            continue;
        }
        if(p.second)
        {
            auto x = info(t, p.first, m - 1, m - 1);
           // cout<<x[4] + 1<<" "<<m - 1<<endl;
            int pos = x[4];
            ans[i] = (ll)c[i] + info(t, pos + 1, m - 1, m - 1)[0];
        }
        else
        {
            auto x = info(t, p.first, m - 1, m - 1);
            int pos = x[2];
            ans[i] = info(t, pos + 1, m - 1, m - 1)[0];
        }
    }
    return ans;
}
//signed main()
//{
//    int n, m;
//    cin>>n>>m;
//    vector<int> c(n);
//    vector<int> l(m), r(m), v(m);
//    for(int i = 0; i < n; i++)
//        cin>>c[i];
//    for(int i = 0; i < m; i++)
//        cin>>l[i]>>r[i]>>v[i];
//    auto a = distribute_candies(c, l, r, v);
//    for(auto i : a)
//        cout<<i<<" ";
//}

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