oj.uz

Submission #809015

# Submission time Handle Problem Language Result Execution time Memory
809015 2023-08-05T14:12:43 Z puppy Distributing Candies (IOI21_candies) C++17
8 / 100
 1242 ms 38896 KB 
#include "candies.h"
#include <vector>
#include <cmath>
#define int long long
using namespace std;

const int inf = 1e18;

struct Node
{
    int mx, mn;
    Node operator+(const Node &nd) const {
        return {max(mx, nd.mx), min(mn, nd.mn)};
    }
};
const Node zero = {-inf, inf};

struct SegTree
{
    vector<Node> tree;
    vector<int> lazy;
    SegTree(int N)
    {
        int sz = 1 << ((int)ceil(log2(N+1)) + 1);
        tree.resize(sz); lazy.resize(sz);
    }
    void push(int s, int e, int node)
    {
        tree[node].mx += lazy[node];
        tree[node].mn += lazy[node];
        if (s != e) {
            for (int i:{2*node, 2*node+1}) {
                lazy[i] += lazy[node];
            }
        }
        lazy[node] = 0;
    }
    void upd(int s, int e, int node, int l, int r, int x)
    {
        push(s, e, node);
        if (e < l || r < s) return;
        if (l <= s && e <= r) {
            lazy[node] += x;
            push(s, e, node);
            return;
        }
        upd(s, (s+e)/2, 2*node, l, r, x);
        upd((s+e)/2+1, e, 2*node+1, l, r, x);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }
    Node query(int s, int e, int node, int l, int r)
    {
        push(s, e, node);
        if (e < l || r < s) return zero;
        if (l <= s && e <= r) return tree[node];
        return query(s, (s+e)/2, 2*node, l, r) + query((s+e)/2+1, e, 2*node+1, l, r);
    }
};

vector<pair<int, int>> upd[200005];

std::vector<signed> distribute_candies(std::vector<signed> c, std::vector<signed> l,
                                    std::vector<signed> r, std::vector<signed> v) {
    int N = c.size();
    int Q = l.size();
    SegTree seg(Q+1);
    for (int i = 0; i < Q; i++) {
        upd[l[i]].push_back(make_pair(i+1, v[i]));
        upd[r[i]+1].push_back(make_pair(i+1, -v[i]));
    }
    vector<signed> ans(N);
    for (int i = 0; i < N; i++) {
        for (pair<int, int> p: upd[i]) {
            seg.upd(0, Q, 1, p.first, Q, p.second);
        }
        Node tmp = seg.query(0, Q, 1, 0, Q);
        if (tmp.mx - tmp.mn <= c[i]) {
            ans[i] = seg.query(0, Q, 1, Q, Q).mx;
        }
        else {
            int l = 0, r = Q;
            while (l < r) {
                int m = l + r + 1 >> 1;
                Node tmp = seg.query(0, Q, 1, m, Q);
                if (tmp.mx - tmp.mn <= c[i]) r = m - 1;
                else l = m;
            }
            Node cur = seg.query(0, Q, 1, l, l), nxt = seg.query(0, Q, 1, l+1, l+1);
            if (cur.mx > nxt.mx) {
                ans[i] = seg.query(0, Q, 1, Q, Q).mx - seg.query(0, Q, 1, l+1, Q).mn;
            }
            else {
                ans[i] = c[i] - (seg.query(0, Q, 1, l+1, Q).mx - seg.query(0, Q, 1, Q, Q).mx);
            }
        }
    }
    return ans;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:83:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |                 int m = l + r + 1 >> 1;
      |                         ~~~~~~^~~

Subtask #1
0 / 3.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1242 ms 37112 KB Output is correct
2 Correct 1151 ms 38896 KB Output is correct
3 Correct 1060 ms 38716 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4988 KB Output is correct
2 Correct 3 ms 4988 KB Output is correct
3 Incorrect 109 ms 30972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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