oj.uz

Submission #683518

# Submission time Handle Problem Language Result Execution time Memory
683518 2023-01-18T16:14:02 Z whqkrtk04 Distributing Candies (IOI21_candies) C++17
8 / 100
 657 ms 46340 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(x, y) uniform_int_distribution<int>(x, y)(rng)

template <typename node_seg, typename node_lazy, typename node_query = node_lazy, typename index_t = int>
class SegtreeLazy {
    private:
    const size_t n;
    std::vector<node_seg> seg;
    std::vector<node_lazy> lazy;

    void prop(const size_t i, const index_t s, const index_t e) {
        if(!(s+1 == e)) {
            lazy[i<<1] += lazy[i];
            seg[i<<1](lazy[i], s, s+e>>1);
            lazy[i<<1|1] += lazy[i];
            seg[i<<1|1](lazy[i], s+e>>1, e);
        }
        lazy[i] = node_lazy::inf();
    }

    void init(const size_t i, const index_t s, const index_t e, const std::vector<node_seg> &A) {
        if(s+1 == e) seg[i] = A[s];
        else {
            init(i<<1, s, s+e>>1, A);
            init(i<<1|1, s+e>>1, e, A);
            seg[i] = seg[i<<1]+seg[i<<1|1];
        }
    }

    void update(const size_t i, const index_t s, const index_t e, const index_t l, const index_t r, const node_query &x) {
        prop(i, s, e);
        if(r <= s || e <= l) return;
        if(l <= s && e <= r) {
            seg[i](x, s, e);
            lazy[i] += x;
        } else {
            update(i<<1, s, s+e>>1, l, r, x);
            update(i<<1|1, s+e>>1, e, l, r, x);
            seg[i] = seg[i<<1]+seg[i<<1|1];
        }
    }

    node_seg query(const size_t i, const index_t s, const index_t e, const index_t l, const index_t r) {
        prop(i, s, e);
        if(r <= s || e <= l) return node_seg::inf();
        if(l <= s && e <= r) return seg[i];
        return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
    }

    index_t search(const size_t i, const index_t s, const index_t e, const function<bool(const node_seg&)> &F, const node_seg &x) {
        prop(i, s, e);
        if(s+1 == e) return s;
        const node_seg y = seg[i<<1|1]+x;
        if(F(y)) return search(i<<1|1, s+e>>1, e, F, x);
        return search(i<<1, s, s+e>>1, F, y);
    }

    public:
    SegtreeLazy(const std::vector<node_seg> &A) : n(A.size()) {
        seg.resize(4*n, node_seg::inf());
        lazy.resize(4*n, node_lazy::inf());
        init(1, 0, n, A);
    }
    void update(const index_t l, const index_t r, const node_query &x) { update(1, 0, n, l, r, x); }
    node_seg query(const index_t l, const index_t r) { return query(1, 0, n, l, r); }
    index_t search(const function<bool(const node_seg&)> &F) { return search(1, 0, n, F, node_seg::inf()); }
    void print() {
        for(auto i : seg) cout << i.mi << " " << i.ma << "  "; cout << "\n";
        for(auto i : lazy) cout << i.x << " "; cout << "\n";
    }
};

struct Node_lazy {
    ll x;
    static Node_lazy inf() { return {0LL}; }
    void operator+=(const Node_lazy &y) { x += y.x; }
};

struct Node_seg {
    ll mi, ma;
    static Node_seg inf() { return {LLINF, 0LL}; }
    Node_seg operator+(const Node_seg &y) { return {min(mi, y.mi), max(ma, y.ma)}; }
    void operator()(const Node_lazy &y, const int l, const int r) { mi += y.x, ma += y.x; }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = v.size();
    vector<vector<int>> L(n), R(n);
    for(int i = 0; i < q; i++) {
        L[l[i]].push_back(i);
        R[r[i]].push_back(i);
    }
    vector<int> ans(n);
    SegtreeLazy<Node_seg, Node_lazy> S(vector<Node_seg>(q+1, {0LL, 0LL}));
    for(int i = 0; i < n; i++) {
        for(auto j : L[i]) S.update(j+1, q+1, {v[j]});
        Node_seg full_range = S.query(0, q+1);
        ll su = S.query(q, q+1).mi;
        if(full_range.ma-full_range.mi <= c[i]) {
            if(full_range.mi < 0) ans[i] = su-full_range.mi;
            else if(full_range.ma > c[i]) ans[i] = c[i]-(full_range.ma-su);
            else ans[i] = su;
        } else {
            int idx = S.search([&](const Node_seg &seg) { return seg.ma-seg.mi > c[i]; });
            full_range = S.query(idx+1, q+1);
            assert(full_range.ma-full_range.mi <= c[i]);
            if(v[idx] < 0) ans[i] = su-full_range.mi;
            else ans[i] = c[i]-(full_range.ma-su);
            //cout << c[i] << " " << idx << " " << pre << " " << v[idx] << "\n";
        }
        for(auto j : R[i]) S.update(j+1, q+1, {-v[j]});
    }
    //cout << S.query(0, q+1).mi << " " << S.query(0, q+1).ma << "\n";
    return ans;
}

Compilation message

candies.cpp: In member function 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::print()':
candies.cpp:85:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   85 |         for(auto i : seg) cout << i.mi << " " << i.ma << "  "; cout << "\n";
      |         ^~~
candies.cpp:85:64: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   85 |         for(auto i : seg) cout << i.mi << " " << i.ma << "  "; cout << "\n";
      |                                                                ^~~~
candies.cpp:86:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   86 |         for(auto i : lazy) cout << i.x << " "; cout << "\n";
      |         ^~~
candies.cpp:86:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   86 |         for(auto i : lazy) cout << i.x << " "; cout << "\n";
      |                                                ^~~~
candies.cpp: In instantiation of 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::init(size_t, index_t, index_t, const std::vector<_Tp>&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int; size_t = long unsigned int]':
candies.cpp:79:9:   required from 'SegtreeLazy<node_seg, node_lazy, node_query, index_t>::SegtreeLazy(const std::vector<_Tp>&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int]'
candies.cpp:111:73:   required from here
candies.cpp:41:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |             init(i<<1, s, s+e>>1, A);
      |                           ~^~
candies.cpp:42:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |             init(i<<1|1, s+e>>1, e, A);
      |                          ~^~
candies.cpp: In instantiation of 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::update(size_t, index_t, index_t, index_t, index_t, const node_query&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int; size_t = long unsigned int]':
candies.cpp:81:80:   required from 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::update(index_t, index_t, const node_query&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int]'
candies.cpp:113:53:   required from here
candies.cpp:54:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |             update(i<<1, s, s+e>>1, l, r, x);
      |                             ~^~
candies.cpp:55:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |             update(i<<1|1, s+e>>1, e, l, r, x);
      |                            ~^~
candies.cpp: In instantiation of 'node_seg SegtreeLazy<node_seg, node_lazy, node_query, index_t>::query(size_t, index_t, index_t, index_t, index_t) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int; size_t = long unsigned int]':
candies.cpp:82:68:   required from 'node_seg SegtreeLazy<node_seg, node_lazy, node_query, index_t>::query(index_t, index_t) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int]'
candies.cpp:114:45:   required from here
candies.cpp:64:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
      |                               ~^~
candies.cpp:64:60: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
      |                                                           ~^~
candies.cpp: In instantiation of 'index_t SegtreeLazy<node_seg, node_lazy, node_query, index_t>::search(size_t, index_t, index_t, const std::function<bool(const node_seg&)>&, const node_seg&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int; size_t = long unsigned int]':
candies.cpp:83:77:   required from 'index_t SegtreeLazy<node_seg, node_lazy, node_query, index_t>::search(const std::function<bool(const node_seg&)>&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int]'
candies.cpp:121:89:   required from here
candies.cpp:71:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         if(F(y)) return search(i<<1|1, s+e>>1, e, F, x);
      |                                        ~^~
candies.cpp:72:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         return search(i<<1, s, s+e>>1, F, y);
      |                                ~^~
candies.cpp: In instantiation of 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::prop(size_t, index_t, index_t) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int; size_t = long unsigned int]':
candies.cpp:48:9:   required from 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::update(size_t, index_t, index_t, index_t, index_t, const node_query&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int; size_t = long unsigned int]'
candies.cpp:81:80:   required from 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::update(index_t, index_t, const node_query&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int]'
candies.cpp:113:53:   required from here
candies.cpp:31:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |             seg[i<<1](lazy[i], s, s+e>>1);
      |                                   ~^~
candies.cpp:33:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |             seg[i<<1|1](lazy[i], s+e>>1, e);
      |                                  ~^~

Subtask #1
0 / 3.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 46340 KB Output is correct
2 Correct 614 ms 46188 KB Output is correct
3 Correct 581 ms 46236 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 202 ms 28960 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 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -