oj.uz

Submission #590090

# Submission time Handle Problem Language Result Execution time Memory
590090 2022-07-05T14:08:46 Z Drew_ Distributing Candies (IOI21_candies) C++17
0 / 100
 930 ms 36236 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;
using pl = pair<ll, ll>;

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

struct Segtree
{
    struct Node
    {
        ll sum, smx, smn;
        
        Node() : sum(0), smx(0), smn(0) {}
        Node(ll val) : sum(val), smx(max(0ll, val)), smn(min(0ll, val)) {}
        
        friend Node operator+ (const Node &lhs, const Node &rhs)
        {
            Node res;
            res.sum = lhs.sum + rhs.sum;
            res.smx = max(lhs.smx + rhs.sum, rhs.smx);
            res.smn = min(lhs.smn + rhs.sum, rhs.smn);
            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)
            {
                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);
    }

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

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<vector<ii>> op(N+1);
    for (int i = 0; i < Q; ++i)
    {
        op[L[i]].pb({i, val[i]});
        op[R[i]+1].pb({i, 0});
    }

    Segtree st = Segtree(Q);

    vector<int> res(N);
    for (int i = 0; i < N; ++i)
    {
        for (auto [id, v] : op[i])
            st.modify(id, v);

        int l = -1, r = Q-1;
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;
            if (st.query(mid, Q-1).f1 >= C[i]) l = mid;
            else r = mid - 1;
        }

        if (l == -1 || st.query(l, l).s2 > 0) res[i] = C[i] + (int)st.query(l+1, Q-1).s2;
        else res[i] = (int)st.query(l+1, Q-1).s2;
    }

    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 7 ms 12500 KB Output is correct
2 Incorrect 7 ms 12584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Incorrect 7 ms 12584 KB Output isn't correct
3 Halted 0 ms 0 KB -