oj.uz

Submission #1065813

# Submission time Handle Problem Language Result Execution time Memory
1065813 2024-08-19T11:58:35 Z Zero_OP Distributing Candies (IOI21_candies) C++17
0 / 100
 846 ms 42852 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), maxtr(n << 2), lazy(n << 2)  {}

    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));
    }
};

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});
        if(r[i] + 1 < n) queriesUpdate[r[i] + 1].push_back({i, -1});
    }

    SegmentTree T(q + 1);
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        for(auto [idQuery, type] : queriesUpdate[i]){
            T.update(1, 0, q, idQuery + 1, q, type * v[idQuery]);
        }

        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;
}

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

    vector<int> ans = distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11});
    for(int i = 0; i < sz(ans); ++i) cout << ans[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 function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:95:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |             int mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 75 ms 28096 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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