oj.uz

Submission #1065886

# Submission time Handle Problem Language Result Execution time Memory
1065886 2024-08-19T12:34:26 Z Zero_OP Distributing Candies (IOI21_candies) C++17
100 / 100
 992 ms 44624 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 4 ms 844 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 844 ms 42596 KB Output is correct
2 Correct 992 ms 42088 KB Output is correct
3 Correct 922 ms 41916 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 161 ms 31456 KB Output is correct
3 Correct 211 ms 9816 KB Output is correct
4 Correct 816 ms 43856 KB Output is correct
5 Correct 843 ms 44112 KB Output is correct
6 Correct 829 ms 44624 KB Output is correct
7 Correct 841 ms 44056 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 93 ms 28312 KB Output is correct
4 Correct 225 ms 8784 KB Output is correct
5 Correct 569 ms 35912 KB Output is correct
6 Correct 587 ms 36572 KB Output is correct
7 Correct 629 ms 37312 KB Output is correct
8 Correct 559 ms 35780 KB Output is correct
9 Correct 610 ms 37316 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 844 ms 42596 KB Output is correct
7 Correct 992 ms 42088 KB Output is correct
8 Correct 922 ms 41916 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 161 ms 31456 KB Output is correct
11 Correct 211 ms 9816 KB Output is correct
12 Correct 816 ms 43856 KB Output is correct
13 Correct 843 ms 44112 KB Output is correct
14 Correct 829 ms 44624 KB Output is correct
15 Correct 841 ms 44056 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 93 ms 28312 KB Output is correct
19 Correct 225 ms 8784 KB Output is correct
20 Correct 569 ms 35912 KB Output is correct
21 Correct 587 ms 36572 KB Output is correct
22 Correct 629 ms 37312 KB Output is correct
23 Correct 559 ms 35780 KB Output is correct
24 Correct 610 ms 37316 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 188 ms 8884 KB Output is correct
27 Correct 156 ms 31056 KB Output is correct
28 Correct 857 ms 42576 KB Output is correct
29 Correct 942 ms 42960 KB Output is correct
30 Correct 852 ms 43088 KB Output is correct
31 Correct 880 ms 43088 KB Output is correct
32 Correct 832 ms 43528 KB Output is correct