oj.uz

Submission #589925

# Submission time Handle Problem Language Result Execution time Memory
589925 2022-07-05T11:56:27 Z Drew_ Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 50612 KB 
#include "candies.h"

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define f1 first
#define s2 second

using ii = pair<int, int>;
using ll = long long;

const int MAX = 2e5 + 69;
const ll inf = (ll)1e18 + 69;

struct Segtree
{
    struct Node
    {
        ll sum;
        ll mx, pmx, smx; // maximum, prefix maximum, suffix maximum
        ll mn, pmn, smn; // minimum, prefix minimum, suffix minimum

        Node() : sum(0), mx(-inf), pmx(mx), smx(mx), mn(inf), pmn(mn), smn(mn) {}
        Node(ll val) : sum(val), mx(val), pmx(mx), smx(mx), mn(val), pmn(mn), smn(mn) {}
        
        friend Node operator+ (const Node &lhs, const Node &rhs)
        {
            Node res;
            res.sum = lhs.sum + rhs.sum;

            res.pmx = max(lhs.pmx, lhs.sum + rhs.pmx);
            res.smx = max(rhs.sum + lhs.smx, rhs.smx);
            res.mx = max({lhs.mx, rhs.mx, lhs.smx + rhs.pmx});

            res.pmn = min(lhs.pmn, lhs.sum + rhs.pmn);
            res.smn = min(rhs.sum + lhs.smn, rhs.smn);
            res.mn = min({lhs.mn, rhs.mn, lhs.smn + rhs.pmn});

            return res;
        }
    };

    int n;
    Node st[1 << 19];

    Segtree() {}
    Segtree(int n_) : n(n_) {}

    inline void modify(int p, ll val)
    {
        const auto modify_ = [&](const auto &self, int node, int l, int r) -> void
        {
            if (l > p || r < p)
                return;
            if (p <= l && r <= p)
            {
                if (val == 0) st[node] = Node();
                else st[node] = Node(val);
                return;
            }
            int mid = (l + r) >> 1;
            self(self, node << 1, l, mid);
            self(self, node << 1 | 1, mid+1, r);
            st[node] = st[node << 1] + st[node << 1 | 1];
        };
        modify_(modify_, 1, 0, n-1);
    }

    // find the rightmost subarray sum which is >= val
    inline ii getmx(ll val)
    {
        if (st[1].mx < val)
            return {-1, -1};

        Node sfx = Node(), pfx = Node();
        const auto getL = [&](const auto &self, int node, int l, int r) -> int
        {
            if (l == r)
                return l;
            int mid = (l + r) >> 1;
            
            Node tmp = st[node << 1 | 1] + sfx;
            if (tmp.mx >= val)
                return self(self, node << 1 | 1, mid+1, r);
            sfx = tmp;
            return self(self, node << 1, l, mid);
        };

        const auto getR = [&](const auto &self, int node, int l, int r, int L) -> int
        {
            int mid = (l + r) >> 1;
            if (r < L)
                return -1;
            if (l < L)
            {
                int ret = self(self, node << 1, l, mid, L);
                if (ret != -1)
                    return ret;

                return self(self, node << 1 | 1, mid+1, r, L);
            }

            Node tmp = pfx + st[node];
            if (tmp.mx < val)
            {
                pfx = tmp;
                return -1;
            }

            if (l == r)
                return l;

            tmp = pfx + st[node << 1];
            if (tmp.mx >= val)
                return self(self, node << 1, l, mid, L);
            else
            {
                pfx = tmp;
                return self(self, node << 1 | 1, mid+1, r, L);
            }
        };

        int L = getL(getL, 1, 0, n-1);
        int R = getR(getR, 1, 0, n-1, L);
        return {L, R};
    }

    // find the rightmost subarray sum which is <= val
    inline ii getmn(ll val)
    {
        if (st[1].mn > val)
            return {-1, -1};

        Node sfx = Node(), pfx = Node();
        const auto getL = [&](const auto &self, int node, int l, int r) -> int
        {
            if (l == r)
                return l;
            int mid = (l + r) >> 1;
            
            Node tmp = st[node << 1 | 1] + sfx;
            if (tmp.mn <= val)
                return self(self, node << 1 | 1, mid+1, r);
            sfx = tmp;
            return self(self, node << 1, l, mid);
        };

        const auto getR = [&](const auto &self, int node, int l, int r, int L) -> int
        {
            int mid = (l + r) >> 1;
            if (r < L)
                return -1;
            if (l < L)
            {
                int ret = self(self, node << 1, l, mid, L);
                if (ret != -1)
                    return ret;

                return self(self, node << 1 | 1, mid+1, r, L);
            }

            Node tmp = pfx + st[node];
            if (tmp.mn > val)
            {
                pfx = tmp;
                return -1;
            }

            if (l == r)
                return l;

            tmp = pfx + st[node << 1];
            if (tmp.mn <= val)
                return self(self, node << 1, l, mid, L);
            else
            {
                pfx = tmp;
                return self(self, node << 1 | 1, mid+1, r, L);
            }
        };

        int L = getL(getL, 1, 0, n-1);
        int R = getR(getR, 1, 0, n-1, L);
        return {L, R};
    }

    inline ll query(int p, int q) // ask for sum
    {
        const auto query_ = [&](const auto &self, int node, int l, int r) -> ll
        {
            if (l > q || r < p)
                return 0;
            if (p <= l && r <= q)
                return st[node].sum;
            int mid = (l + r) >> 1;
            return self(self, node << 1, l, mid) + self(self, node << 1 | 1, mid+1, r);
        };
        return query_(query_, 1, 0, n-1);
    }
};

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> val) 
{
    int N = (int)C.size(), Q = (int)L.size();

    vector<int> id = { 0 };
    for (int i = 1; i < Q; ++i)
    {
        if ((val[i] > 0) == (val[i-1] > 0))
            id.pb(id.back());
        else id.pb(id.back() + 1);
    }

    vector<array<int, 4>> vec;
    for (int i = 0; i < Q; ++i)
        vec.pb({L[i], R[i], val[i], id[i]});
    sort(vec.begin(), vec.end());

    int sz = (int)id.size();
    vector<ll> cur(sz, 0);
    Segtree st = Segtree(sz);

    vector<int> res(N);
    priority_queue<array<int, 3>> pq;
    for (int i = 0, j = 0; i < N; ++i)
    {
        while (j < Q && i >= vec[j][0])
        {
            cur[vec[j][3]] += vec[j][2];
            st.modify(vec[j][3], cur[vec[j][3]]);

            pq.push({-vec[j][1], vec[j][2], vec[j][3]});
            ++j;
        }
        while (!pq.empty() && i > -pq.top()[0])
        {
            cur[pq.top()[2]] -= pq.top()[1];
            st.modify(pq.top()[2], cur[pq.top()[2]]);
            pq.pop();
        }

        cerr << "st: ";
        for (int x = 0; x < sz; ++x)
            cerr << st.query(x, x) << " \n"[x == sz-1];
        // exit(0);

        auto [l, r] = st.getmx(C[i]);
        if (l == -1)
        {
            auto [p, q] = st.getmn(0);
            res[i] = (int)st.query(q+1, sz-1);
        }
        else
        {
            auto [p, q] = st.getmn(-C[i]);
            if (r < p)
                res[i] = (int)st.query(q+1, sz-1);
            else
            {
                auto [a, b] = st.getmx(0);
                if (q < a)
                    res[i] = C[i] + (int)st.query(b+1, sz-1);
                else res[i] = C[i] + (int)st.query(r+1, sz-1);
            }
        }
    }

    return res;
}

// int main() {
//     int n;
//     assert(1 == scanf("%d", &n));
//     std::vector<int> c(n);
//     for(int i = 0; i < n; ++i) {
//         assert(scanf("%d", &c[i]) == 1);
//     }

//     int q;
//     assert(1 == scanf("%d", &q));
//     std::vector<int> l(q), r(q), v(q);
//     for(int i = 0; i < q; ++i) {
//         assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
//     }

//     std::vector<int> ans = distribute_candies(c, l, r, v);

//     for(int i = 0; i < n; ++i) {
//         if (i > 0) {
//             printf(" ");
//         }
//         printf("%d", ans[i]);
//     }
//     printf("\n");
//     fclose(stdout);
//     return 0;
// }

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29148 KB Output is correct
2 Correct 14 ms 28996 KB Output is correct
3 Incorrect 64 ms 29248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5087 ms 50612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29148 KB Output is correct
2 Correct 14 ms 28996 KB Output is correct
3 Incorrect 64 ms 29248 KB Output isn't correct
4 Halted 0 ms 0 KB -