Submission #493075

#	Time	Username	Problem	Language	Result	Execution time	Memory
493075		qwerasdfzxcl	Distributing Candies (IOI21_candies)	C++17	100 / 100	714 ms	47240 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const ll INF = 1e18;
struct Seg{
    pair<ll, ll> tree[800800];
    ll lazy[800800];
    pair<ll, ll> combine(pair<ll, ll> x, pair<ll, ll> y){
        return pair<ll, ll>(max(x.first, y.first), min(x.second, y.second));
    }
    void propagate(int i, int l, int r){
        tree[i].first += lazy[i];
        tree[i].second += lazy[i];
        if (l!=r) lazy[i<<1] += lazy[i], lazy[i<<1|1] += lazy[i];
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, ll x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] += x;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, x);
        update(i<<1|1, m+1, r, s, e, x);
        tree[i] = combine(tree[i<<1], tree[i<<1|1]);
    }
    pair<ll, ll> query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if (r<s || e<l) return {-INF, INF};
        if (s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return combine(query(i<<1, l, m, s, e), query(i<<1|1, m+1, r, s, e));
    }
    int left_bound(int i, int l, int r, int x, pair<ll, ll> cur){
        propagate(i, l, r);
        assert(cur.first-cur.second<=x);
        auto p = combine(cur, tree[i]);
        if (p.first-p.second<=x) return -1;
        if (l==r) return l;

        int m = (l+r)>>1;
        int tmp = left_bound(i<<1|1, m+1, r, x, cur);
        if (tmp!=-1) return tmp;
        return left_bound(i<<1, l, m, x, combine(cur, tree[i<<1|1]));
    }
}tree;
vector<int> qb[200200], qe[200200];

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    int q = v.size();
    vector<int> ret(n);
    for (int i=0;i<q;i++){
        qb[l[i]+1].push_back(i+1);
        qe[r[i]+1].push_back(i+1);
    }

    for (int i=1;i<=n;i++){
        for (auto &x:qe[i-1]) tree.update(1, 0, q, x, q, -v[x-1]);
        for (auto &x:qb[i]) tree.update(1, 0, q, x, q, v[x-1]);

        int idx = tree.left_bound(1, 0, q, c[i-1], {-INF, INF});
        //printf("%d: %d %lld %lld\n", i, idx, tree.tree[1].first, tree.tree[1].second);
        if (idx==-1) ret[i-1] = tree.query(1, 0, q, q, q).first - tree.query(1, 0, q, 0, q).second;
        else{
            ll tmp = tree.query(1, 0, q, idx, idx).first;
            auto p = tree.query(1, 0, q, idx, q);
            if (tmp==p.first) ret[i-1] = tree.query(1, 0, q, q, q).first - p.second;
            else if (tmp==p.second) ret[i-1] = c[i-1] - p.first + tree.query(1, 0, q, q, q).first;
            else exit(1);
        }
    }

    return ret;
}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33