oj.uz

Submission #802931

# Submission time Handle Problem Language Result Execution time Memory
802931 2023-08-02T15:57:03 Z SamAnd Distributing Candies (IOI21_candies) C++17
67 / 100
 414 ms 23812 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 200005;

int n, q, C;

struct ban
{
    int ans, l, r;
    ban(){}
    ban(int ans, int l, int r)
    {
        this->ans = ans;
        this->l = l;
        this->r = r;
    }
};

ban mer(const ban& l, const ban& r)
{
    ban res;
    if (l.ans <= r.l)
        res.ans = r.ans;
    else if (l.ans >= r.r)
        res.ans = r.ans + r.r - r.l;
    else
        res.ans = r.ans + l.ans - r.l;
    res.l = l.l + max(0, r.l - l.ans);
    res.r = l.r - max(0, l.ans + l.r - l.l - r.r);
    if (res.l > res.r)
        res.l = res.r = 0;
    return res;
}

ban t[N * 4];
void bil(int tl, int tr, int pos)
{
    t[pos] = ban(0, 0, C);
    if (tl == tr)
        return;
    int m = (tl + tr) / 2;
    bil(tl, m, pos * 2);
    bil(m + 1, tr, pos * 2 + 1);
}

void ubd(int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        y = min(y, C);
        y = max(y, -C);
        if (y == 0)
            t[pos] = ban(0, 0, C);
        else if (y > 0)
            t[pos] = ban(y, 0, C - y);
        else
            t[pos] = ban(0, -y, C);
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, pos * 2);
    else
        ubd(m + 1, tr, x, y, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}

vector<int> v[N];
vector<pair<int, int> > p;

int c[N * 4];
void shi(int pos)
{
    if (c[pos] == N)
        return;
    c[pos * 2] = c[pos * 2 + 1] = c[pos];
    c[pos] = N;
}
void ubd(int tl, int tr, int l, int r, int y, int pos)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        c[pos] = y;
        return;
    }
    shi(pos);
    int m = (tl + tr) / 2;
    ubd(tl, m, l, min(m, r), y, pos * 2);
    ubd(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
}
int qry(int tl, int tr, int x, int pos)
{
    if (tl == tr)
        return c[pos];
    shi(pos);
    int m = (tl + tr) / 2;
    if (x <= m)
        return qry(tl, m, x, pos * 2);
    else
        return qry(m + 1, tr, x, pos * 2 + 1);
}

vector<ll> pr;

int qryy(int i, int q, const vector<int>& v)
{
    int j = qry(0, n - 1, i, 1);
    int s;
    if (j == -1 || v[j] < 0)
        s = 0;
    else
        s = p[i].fi;
    return s + pr[q] - pr[j + 1];
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> vv) {

    n = sz(c);
    q = sz(l);
    vector<int> ans(n);

    if (n <= 2000 && q <= 2000)
    {
        for (int i = 0; i < n; ++i)
            ans[i] = 0;
        for (int i = 0; i < q; ++i)
        {
            for (int j = l[i]; j <= r[i]; ++j)
            {
                ans[j] += vv[i];
                ans[j] = max(ans[j], 0);
                ans[j] = min(ans[j], c[j]);
            }
        }
        return ans;
    }

    bool f = true;
    for (int i = 0; i < q; ++i)
    {
        if (vv[i] < 0)
        {
            f = false;
            break;
        }
    }
    if (f)
    {
        vector<ll> p;
        p.assign(n + 1, 0);
        for (int i = 0; i < q; ++i)
        {
            p[l[i]] += vv[i];
            p[r[i] + 1] -= vv[i];
        }
        for (int i = 0; i < n; ++i)
        {
            if (i)
                p[i] += p[i - 1];
            ans[i] = min(c[i] * 1LL, p[i]);
        }
        return ans;
    }

    f = true;
    for (int i = 0; i < n; ++i)
    {
        if (c[i] != c[0])
        {
            f = false;
            break;
        }
    }
    if (f)
    {
        for (int i = 0; i < q; ++i)
        {
            v[l[i]].push_back((i + 1));
            v[r[i] + 1].push_back(-(i + 1));
        }

        C = c[0];
        bil(0, q - 1, 1);

        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < sz(v[i]); ++j)
            {
                if (v[i][j] > 0)
                {
                    --v[i][j];
                    ubd(0, q - 1, v[i][j], vv[v[i][j]], 1);
                }
                else
                {
                    v[i][j] *= -1;
                    --v[i][j];
                    ubd(0, q - 1, v[i][j], 0, 1);
                }
            }
            ans[i] = t[1].ans;
        }
    }
    else
    {
        for (int i = 0; i < n; ++i)
        {
            p.push_back(m_p(c[i], i));
        }
        sort(all(p));

        pr.push_back(0);
        for (int i = 0; i < q; ++i)
            pr.push_back(pr.back() + vv[i]);
        ubd(0, n - 1, 0, n - 1, -1, 1);
        for (int i = 0; i < q; ++i)
        {
            if (vv[i] > 0)
            {
                int l = 0, r = n - 1;
                int u = -1;
                while (l <= r)
                {
                    int m = (l + r) / 2;
                    if (qryy(m, i, vv) + vv[i] >= p[m].fi)
                    {
                        u = m;
                        l = m + 1;
                    }
                    else
                        r = m - 1;
                }
                ubd(0, n - 1, 0, u, i, 1);
            }
            else
            {
                int l = 0, r = n - 1;
                int u = -1;
                while (l <= r)
                {
                    int m = (l + r) / 2;
                    if (qryy(m, i, vv) + vv[i] <= 0)
                    {
                        u = m;
                        l = m + 1;
                    }
                    else
                        r = m - 1;
                }
                ubd(0, n - 1, 0, u, i, 1);
            }
        }

        for (int i = 0; i < n; ++i)
        {
            ans[p[i].se] = qryy(i, q, vv);
        }
    }

    return ans;
}

/*
10
1 2 3 4 5 6 7 8 9 10
4
0 9 10
0 9 -5
0 9 1
0 9 1
*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5024 KB Output is correct
5 Correct 5 ms 5036 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 13520 KB Output is correct
2 Correct 84 ms 17596 KB Output is correct
3 Correct 82 ms 17456 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 175 ms 18124 KB Output is correct
3 Correct 42 ms 8596 KB Output is correct
4 Correct 266 ms 23700 KB Output is correct
5 Correct 281 ms 23716 KB Output is correct
6 Correct 268 ms 23812 KB Output is correct
7 Correct 257 ms 23764 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 152 ms 11912 KB Output is correct
4 Correct 72 ms 11268 KB Output is correct
5 Correct 401 ms 17328 KB Output is correct
6 Correct 410 ms 17280 KB Output is correct
7 Correct 396 ms 17344 KB Output is correct
8 Correct 414 ms 17364 KB Output is correct
9 Correct 81 ms 13528 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5024 KB Output is correct
5 Correct 5 ms 5036 KB Output is correct
6 Correct 83 ms 13520 KB Output is correct
7 Correct 84 ms 17596 KB Output is correct
8 Correct 82 ms 17456 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 175 ms 18124 KB Output is correct
11 Correct 42 ms 8596 KB Output is correct
12 Correct 266 ms 23700 KB Output is correct
13 Correct 281 ms 23716 KB Output is correct
14 Correct 268 ms 23812 KB Output is correct
15 Correct 257 ms 23764 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 152 ms 11912 KB Output is correct
19 Correct 72 ms 11268 KB Output is correct
20 Correct 401 ms 17328 KB Output is correct
21 Correct 410 ms 17280 KB Output is correct
22 Correct 396 ms 17344 KB Output is correct
23 Correct 414 ms 17364 KB Output is correct
24 Correct 81 ms 13528 KB Output is correct
25 Correct 2 ms 5016 KB Output is correct
26 Incorrect 74 ms 12364 KB Output isn't correct
27 Halted 0 ms 0 KB -