제출 #444222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444222		hiliy	사탕 분배 (IOI21_candies)	C++17	100 / 100	1402 ms	50180 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct segtree{
    int sz;
    vector<ll> sum, mins, maxs, sumpush;
    segtree(int maxn)
    {
        sz = maxn*4 + 4;
        sum.resize(sz);
        mins = maxs = sumpush = sum;
    }
    void push(int v, int l, int r)
    {
        mins[v] += sumpush[v];
        maxs[v] += sumpush[v];
        sum[v] += (ll)(r - l + 1)*sumpush[v];
        if(l != r)
            sumpush[v*2] += sumpush[v], sumpush[v*2 + 1] += sumpush[v];
        sumpush[v] = 0;
    }
    void add(int v, int l, int r, int l1, int r1, int val)
    {
        push(v, l, r);
        if(l > r1 || l1 > r)
            return;
        if(l1 <= l && r <= r1)
        {
            sumpush[v] += val;
            push(v, l, r);
            return;
        }
        add(v*2, l, (l + r) / 2, l1, r1, val), add(v*2 + 1, (l + r) / 2 + 1, r, l1, r1, val);
        sum[v] = sum[v * 2] + sum[v * 2 + 1];
        mins[v] = min(mins[v * 2], mins[v * 2 + 1]);
        maxs[v] = max(maxs[v * 2], maxs[v * 2 + 1]);
    }
    pair<int, bool> getpos(int v, int l, int r, int razn, ll minr, ll maxr)
    {
        push(v, l, r);
        if(l == r)
        {
            if(mins[v] <= minr)
                return {l, 0};
            else
                return {l, 1};
        }
       // cout<<razn<<" "<<l<<" "<<r<<endl;
        push(v * 2, l, (l + r) / 2);
        push(v * 2 + 1, (l + r) / 2 + 1, r);
        if(abs(min(minr, mins[v * 2 + 1]) - max(maxr, maxs[v * 2 + 1])) >= razn)
            return getpos(v * 2 + 1, (l + r) / 2 + 1, r, razn, minr, maxr);
        return getpos(v * 2, l, (l + r) / 2, razn, min(minr, mins[v * 2 + 1]), max(maxr, maxs[v * 2 + 1]));
    }
    int wheremin(int v, int l, int r, ll need)
    {
        push(v, l, r);
        if(l == r)
            return l;
        push(v * 2, l, (l + r) / 2);
        push(v * 2 + 1, (l + r) / 2 + 1, r);
        if(mins[v * 2 + 1] <= need)
            return wheremin(v * 2 + 1, (l + r ) / 2 + 1, r, need);
        return wheremin(v * 2, l, (l + r) / 2, need);
    }
    int wheremax(int v, int l, int r, ll need)
    {
        push(v, l, r);
        if(l == r)
            return l;
        push(v * 2, l, (l + r) / 2);
        push(v * 2 + 1, (l + r) / 2 + 1, r);
        if(maxs[v * 2 + 1] >= need)
            return wheremax(v * 2 + 1, (l + r ) / 2 + 1, r, need);
        return wheremax(v * 2, l, (l + r) / 2, need);
    }
    ll getmin(int v, int l, int r, int l1, int r1)
    {
        push(v, l, r);
        if(l > r1 || l1 > r || l1 > r1)
            return 1e18;
        if(l1 <= l && r <= r1)
            return mins[v];
        return min(getmin(v * 2, l, (l + r) / 2, l1, r1), getmin(v * 2 + 1, (l + r) / 2 + 1, r, l1, r1));
    }
    ll getmax(int v, int l, int r, int l1, int r1)
    {
        push(v, l, r);
        if(l > r1 || l1 > r || l1 > r1)
            return -1e18;
        if(l1 <= l && r <= r1)
            return maxs[v];
        return max(getmax(v * 2, l, (l + r) / 2, l1, r1), getmax(v * 2 + 1, (l + r) / 2 + 1, r, l1, r1));
    }
    ll getsum(int v, int l, int r, int l1, int r1)
    {
        push(v, l, r);
        if(l > r1 || l1 > r || l1 > r1)
            return 0;
        if(l1 <= l && r <= r1)
            return sum[v];
        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);
    for(int i = 0; i < m; i++)
    {
        in[l[i]].push_back(i);
        in[r[i] + 1].push_back(i);
    }
    segtree t(m + 1);
    vector<int> active(m);
    vector<int> ans(n);
    for(int i = 0; i < n; i++)
    {
        for(auto j : in[i])
        {
            active[j] ^= 1;
            if(active[j])
                t.add(1, 0, m, j + 1, m, v[j]);
            else
                t.add(1, 0, m, j + 1, m, -v[j]);
        }
        t.push(1, 0, m);
        int razn = min((ll)c[i], t.maxs[1] - t.mins[1]);
        auto p = t.getpos(1, 0, m, razn, 1e18, -1e18);
        if(!p.second)
        {
            int pos = t.wheremax(1, 0, m, t.getmax(1, 0, m, p.first, m));
            ans[i] = razn + t.getsum(1, 0, m, m, m) - t.getsum(1, 0, m, pos, pos);
        }
        else
        {
          //  cout<<i<<" "<<t.getmin(1, 0, m, p.first, m)<<endl;
            int pos = t.wheremin(1, 0, m, t.getmin(1, 0, m, p.first, m));
            ans[i] = t.getsum(1, 0, m, m, m) - t.getsum(1, 0, m, pos, pos);
        }
    }
    return ans;
}
/*signed main()
{
    int n, m;
    cin>>n;
    vector<int> c(n);
    for(int i = 0; i < n; i++)
        cin>>c[i];
    cin>>m;
    vector<int> l(m), r(m), v(m);
    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: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33