Submission #590096

#	Time	Username	Problem	Language	Result	Execution time	Memory
590096		Drew_	Distributing Candies (IOI21_candies)	C++17	Compilation error	0 ms	0 KiB

candies

#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, lhs.sum + rhs.smx);
            res.smn = min(lhs.smn, lhs.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;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccUziNhZ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccoS0n2W.o:candies.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status