oj.uz

Submission #444006

# Submission time Handle Problem Language Result Execution time Memory
444006 2021-07-12T20:54:51 Z hiliy Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 91204 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> merge(vector<ll> v1, vector<ll> v2)
{
    vector<ll> ans(7);
    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];
    ans[5] = min(min(v1[5], v2[5]), min(ans[1], v2[1] + v1[0] - v1[3]));
    ans[6] = max(max(v1[6], v2[6]), max(ans[3], v2[3] + v1[0] - v1[1]));
    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]
    //minrazn - data[5]
    //maxrazn - data[6]
    segtree(vector<int> v)
    {
        val = v;
        sz = val.size() * 4 + 2;
        active.resize(sz);
        data.resize(sz, vector<ll>(7));
    }
    void change(int v, int l, int r, int pos)
    {
        if(l > pos || r < pos)
            return;
        if(l == r)
        {
            active[v] ^= 1;
            if(active[v])
            {
                data[v][0] = data[v][1] = data[v][3] = val[l];
                data[v][5] = val[l];
                data[v][6] = val[l];
                data[v][2] = l;
                data[v][4] = l;
            }
            else
                data[v] = vector<ll>(7), data[v][2] = data[v][4] = l;
            return;
        }
        change(v*2, l, (l + r) / 2, pos), change(v*2 + 1, (l + r) / 2 + 1, r, pos);
        data[v] = merge(data[v*2], data[v*2 + 1]);
    }
    pair<int, bool> getans(int v, int l, int r, int needmin, int needmax, vector<ll> d)
    {
        if(l == r)
        {
            if(d[0] == -1e18)
                d = data[v];
            else
                d = merge(data[v], d);
            if(d[5] <= needmin)
                return {l, 0};
            else if(d[6] >= needmax)
                return {l, 1};
            return {-1, 0};
        }
        vector<ll> c;
        if (d[0] == -1e18)
            c = data[v * 2 + 1];
        else
            c = merge(data[v * 2 + 1], d);
        if(c[5] <= needmin || c[6] >= 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)
            return;
        if(l1 <= l && r <= r1)
        {
            if(d[0] == -1e18)
                d = data[v];
            else
                d = merge(d, data[v]);
            return;
        }
        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(7);
    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, d[2] = r, d[4] = r;
    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);
    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 < m; i++)
    {
        t.change(1, 0, m - 1, i);
        t.change(1, 0, m - 1, i);
    }
    for(int i = 0; i < n; i++)
    {
        for(auto j : in[i])
            t.change(1, 0, m - 1, j);
        vector<ll> d(7);
        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);
            ll sum = c[i];
            for(int j = x[4] + 1; j < m; j++) {
                sum += info(t, j, j, m - 1)[0];
            }
            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;
    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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 11 ms 1100 KB Output is correct
4 Correct 12 ms 1032 KB Output is correct
5 Correct 21 ms 1100 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3334 ms 91204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 324 KB Output is correct
2 Execution timed out 5039 ms 80616 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 11 ms 1100 KB Output is correct
4 Correct 12 ms 1032 KB Output is correct
5 Correct 21 ms 1100 KB Output is correct
6 Incorrect 3334 ms 91204 KB Output isn't correct
7 Halted 0 ms 0 KB -