Submission #1065886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065886		Zero_OP	Distributing Candies (IOI21_candies)	C++17	100 / 100	992 ms	44624 KiB

candies

#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define dbg(v) "[" #v " = " << (v) << "]"
#define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }  return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        } return false;
    }

template<int dimension, typename T>
struct tensor : public vector<tensor<dimension - 1, T>> {
    static_assert(dimension > 0, "Dimension must be positive !\n");
    template<typename... Args>
    tensor(int n = 0, Args... args) : vector<tensor<dimension - 1, T>> (n, tensor<dimension - 1, T>(args...)) {}
};

template<typename T>
struct tensor<1, T> : public vector<T> {
    tensor(int n = 0, T val = T()) : vector<T>(n, val) {}
};

struct SegmentTree{
    vector<long long> mintr, maxtr, lazy;
    SegmentTree(int n) : mintr(n << 2, 0), maxtr(n << 2, 0), lazy(n << 2, 0)  {}

    void apply(int id, long long val){
        mintr[id] += val;
        maxtr[id] += val;
        lazy[id] += val;
    }

    void pushDown(int id){
        if(lazy[id] != 0){
            apply(id << 1, lazy[id]);
            apply(id << 1 | 1, lazy[id]);
            lazy[id] = 0;
        }
    }

    void update(int id, int l, int r, int u, int v, long long val){
        if(u <= l && r <= v) apply(id, val);
        else{
            int mid = l + r >> 1;
            pushDown(id);
            if(u <= mid) update(id << 1, l, mid, u, v, val);
            if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, val);
            mintr[id] = min(mintr[id << 1], mintr[id << 1 | 1]);
            maxtr[id] = max(maxtr[id << 1], maxtr[id << 1 | 1]);
        }
    }

    pair<long long, long long> query(int id, int l, int r, int u, int v){
        if(v < l || u > r) return {LLONG_MAX, LLONG_MIN};
        if(u <= l && r <= v) return {mintr[id], maxtr[id]};
        int mid = l + r >> 1;
        pushDown(id);
        pair<long long, long long> lt = query(id << 1, l, mid, u, v);
        pair<long long, long long> rt = query(id << 1 | 1, mid + 1, r, u, v);
        return make_pair(min(lt.first, rt.first), max(lt.second, rt.second));
    }

    void debug(int id, int l, int r){
        cout << id << dbg(l) << ' ' << dbg(r) << ' '<< dbg(mintr[id]) << ' ' << dbg(maxtr[id]) << '\n';
        if(l < r){
            int mid = l + r >> 1;
            pushDown(id);
            debug(id << 1, l, mid);
            debug(id << 1 | 1, mid + 1, r);
        }
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){

    int n = (int)c.size(), q = (int)l.size();
    tensor<2, pair<int, int>> queriesUpdate(n);
    for(int i = 0; i < q; ++i){
        queriesUpdate[l[i]].push_back({i + 1, v[i]});
        if(r[i] + 1 < n) queriesUpdate[r[i] + 1].push_back({i + 1, -v[i]});
    }

    SegmentTree T(q + 1);
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        for(auto [pos, val] : queriesUpdate[i]){
            T.update(1, 0, q, pos, q, val);
//            cout << pos << ' ' << q << ' ' << val << "!!\n";
        }

//        T.debug(1, 0, q);
//        for(int j = 0; j <= q; ++j){
//            cout << T.query(1, 0, q, j, j).first << ' ';
//        }
//        cout << '\n';

        int l = 0, r = q, cut = -1;
        while(l <= r){
            int mid = l + r >> 1;
            long long suffix_min, suffix_max;
            tie(suffix_min, suffix_max) = T.query(1, 0, q, mid, q);
            if(suffix_max - suffix_min > c[i]){
                cut = mid;
                l = mid + 1;
            } else r = mid - 1;
        }

        long long sum_t = T.query(1, 0, q, q, q).first;

        if(cut == -1){
            a[i] = sum_t - T.query(1, 0, q, 0, q).first;
        } else{
            long long suffix_min_at_cut, suffix_max_at_cut;
            tie(suffix_min_at_cut, suffix_max_at_cut) = T.query(1, 0, q, cut, q);

            if(T.query(1, 0, q, cut, cut).first < sum_t){
                a[i] = c[i] - (suffix_max_at_cut - sum_t);
            } else{
                a[i] = sum_t - suffix_min_at_cut;
            }
        }
    }

    return a;
}

vector<int> brute(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
    for(int i = 0; i < sz(c); ++i) cout << c[i] << ' '; cout << '\n';
    for(int i = 0; i < sz(l); ++i) cout << l[i] << ' ' << r[i] << ' ' << v[i] << '\n';
    cout << '\n';

    int n = sz(c), q = sz(l);
    vector<int> ans(n);

    for(int i = 0; i < q; ++i){
        for(int j = l[i]; j <= r[i]; ++j){
            ans[j] = max(0, min(c[j], ans[j] + v[i]));
        }
    }

    return ans;
}

#ifdef LOCAL

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int random(int l, int r){
    return uniform_int_distribution<int>(l, r)(rng);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

//    int n = random(5, 5), q = random(1, 3);
//    vector<int> c(n);
//    vector<int> l(q), r(q), v(q);
//
//    for(int i = 0; i < n; ++i) c[i] = random(1, 100);
//    for(int i = 0; i < q; ++i){
//        l[i] = random(0, n - 1);
//        r[i] = random(0, n - 1);
//        if(l[i] > r[i]) swap(l[i], r[i]);
//        v[i] = random(-10, +10);
//        while(v[i] == 0) v[i] = random(-10, +10);
//    }
//
//    cout << "c array : ";
//    for(int i = 0; i < n; ++i){
//        cout << c[i] << ' ';
//    }
//    cout << '\n';
//
//    cout << "queries : \n";
//    for(int i = 0; i < q; ++i){
//        cout << l[i] << ' ' << r[i] << ' ' << v[i] << '\n';
//    }
//    cout << '\n';

    vector<int> c = {95, 55, 29, 40, 29};
    vector<int> l = {0, 0, 0};
    vector<int> r = {1, 1, 4};
    vector<int> v = {-1, -3, -9};

    vector<int> ans = distribute_candies(c, l, r, v);
//    vector<int> cor = brute(c, l, r, v);
    for(int i = 0; i < sz(ans); ++i) cout << ans[i] << ' '; cout << '\n';
//    for(int i = 0; i < sz(cor); ++i) cout << cor[i] << ' '; cout << '\n';

    return 0;
}
#endif

Compilation message (stderr)

candies.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, long long int)':
candies.cpp:58:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |             int mid = l + r >> 1;
      |                       ~~^~~
candies.cpp: In member function 'std::pair<long long int, long long int> SegmentTree::query(int, int, int, int, int)':
candies.cpp:70:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         int mid = l + r >> 1;
      |                   ~~^~~
candies.cpp: In member function 'void SegmentTree::debug(int, int, int)':
candies.cpp:80:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |             int mid = l + r >> 1;
      |                       ~~^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:113:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |             int mid = l + r >> 1;
      |                       ~~^~~
candies.cpp: In function 'std::vector<int> brute(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:142:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  142 |     for(int i = 0; i < sz(c); ++i) cout << c[i] << ' '; cout << '\n';
      |     ^~~
candies.cpp:142:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  142 |     for(int i = 0; i < sz(c); ++i) cout << c[i] << ' '; cout << '\n';
      |                                                         ^~~~

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