Submission #442923

#	Time	Username	Problem	Language	Result	Execution time	Memory
442923		hiliy	Distributing Candies (IOI21_candies)	C++17	0 / 100	1469 ms	67204 KiB

candies

#include <bits/stdc++.h>
#include <candies.h>
using namespace std;
struct segtree{
    int sz;
    vector<int> val;
    vector<bool> on;
    vector<bool> blocked;
    //vector<int> maxpref, minpref, sum, maxrazn, minrazn;
    vector<vector<int>> rec;
    segtree(vector<int> v)
    {
        val = v;
        sz = 4*(v.size() + 2);
        on.resize(sz);
        rec.resize(sz, vector<int>(5));
    }
    vector<int> recalc(vector<int> &v1, vector<int> &v2)
    {
        vector<int> ans(5);
        ans[2] = v1[2] + v2[2];
        ans[0] = max(v1[0], v2[0] + v1[2]);
        ans[1] = min(v1[1], v2[1] + v1[2]);
        ans[3] = max(max(v1[3], v2[3]), v2[0] + v1[2] - v1[1]);
        ans[4] = min(min(v1[4], v2[4]), v2[1] + v1[2] - v1[0]);
        return ans;
    }
    void change(int v, int l, int r, int pos)
    {
        if(pos < l || pos > r)
            return;
        if(l == r)
        {
            on[v] = !on[v];
            if(on[v])
            {
                rec[v][2] = val[l];
                rec[v][0] = val[l];
                rec[v][1] = val[l];
                rec[v][3] = rec[v][4] = val[l];
               // cout<<rec[v][0]<<" "<<rec[v][1]<<" "<<rec[v][2]<<" "<<rec[v][3]<<" "<<rec[v][4]<<endl;
            }
            else
                rec[v] = {0, 0, 0, 0, 0};
            return;
        }
        change(v*2, l, (l + r) / 2, pos), change(v*2 + 1, (l + r) / 2 + 1, r, pos);
        rec[v] = recalc(rec[v*2], rec[v*2 + 1]);
    }
    int getans(int v, int l, int r, int needmin, int needmax, vector<int> &mrg)
    {
        if(l == r)
            return l;
        if(rec[v*2 + 1][0] == 0 && rec[v*2 + 1][1] == 0)
            return getans(v*2, l, (l + r) / 2, needmin, needmax, mrg);
        vector<int> c = recalc(mrg, rec[v*2]);
        if(rec[v*2 + 1][0] + c[2] - c[1] >= needmax || rec[v*2+1][1] + c[2] - c[0] <= needmin || rec[v*2 + 1][3] >= needmax || rec[v*2 + 1][4] <= needmin)
            return getans(v * 2 + 1, (l + r) / 2 + 1, r, needmax, needmin, c);
        return getans(v, l, (l + r) / 2, needmin, needmax, mrg);
    }
    int getsum(int v, int l, int r, int l1, int r1)
    {
        if(l > r1 || l1 > r || l1 > r1)
            return 0;
        if(l1 <= l && r <= r1)
            return rec[v][2];
        return getsum(v*2, l, (l + r) / 2, l1, r1) + getsum(v*2 + 1, (l + r) / 2 + 1, r, l1, r1);
    }
};
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);
    segtree t(v);
    for(int i = 0; i < m; i++)
    {
        in[l[i]].push_back(i);
        in[r[i] + 1].push_back(i);
    }
    vector<int> ans(n);
    for(int i = 0; i < n; i++)
    {
        for(auto j : in[i])
            t.change(1, 0, m - 1, j);
        int mins = t.rec[1][4], maxs = min(t.rec[1][3], c[i]);
        mins = -maxs;
        if(mins == 0)
        {
            ans[i] = min(t.rec[1][2], c[i]);
            continue;
        }
        vector<int> mrg(5);
        int pos = t.getans(1, 0, m - 1, mins, maxs, mrg);
        ans[i] = t.getsum(1, 0, m - 1, pos + 1, m - 1);
        if(t.getsum(1, 0, m - 1, pos, pos) > 0)
            ans[i] += maxs;
    }
    return ans;
}

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