oj.uz

Submission #494114

# Submission time Handle Problem Language Result Execution time Memory
494114 2021-12-14T11:50:41 Z maksim1744 Distributing Candies (IOI21_candies) C++17
100 / 100
 634 ms 42808 KB 
/*
    author:  Maksim1744
    created: 07.12.2021 02:14:12
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#endif

struct item {
    ll mn = 1e18;
    ll mx = -1e18;
    ll mod = 0;
    int imn = -1, imx = -1;

    template<typename T>
    void init(const T &t, int l, int r) {
        imn = imx = l;
        mn = mx = t;
    }

    void update(const item &first, const item &second, int l, int r) {
        mn = min(first.mn, second.mn);
        mx = max(first.mx, second.mx);
        if (first.mn >= second.mn)
            imn = second.imn;
        else
            imn = first.imn;
        if (first.mx <= second.mx)
            imx = second.imx;
        else
            imx = first.imx;
    }

    static item merge(const item &first, const item &second, int l, int r) {
        item res;
        res.update(first, second, l, r);  // careful with different lengths
        return res;
    }

    template<typename Modifier>
    void modify(const Modifier &m, int l, int r) {
        mn += m;
        mx += m;
        mod += m;
    }

    void push(item &first, item &second, int l, int r) {
        int m = (l + r) / 2;
        first.modify(mod, l, m);
        second.modify(mod, m + 1, r);
        mod = 0;
    }
};

string to_string(const item &i) {
    stringstream ss;
    ss << "[" << "]";
    return ss.str();
}
ostream& operator << (ostream &o, const item &i) {
    return o << to_string(i);
}

struct segtree {
    vector<item> tree;
    int n = 1;

    segtree(int n = 1) : n(n) {
        tree.resize(1 << (__lg(max(1, n - 1)) + 2));
    }

    template<typename T>
    void build(const vector<T> &v, int i, int l, int r) {
        if (l == r) {
            tree[i].init(v[l], l, r);
            return;
        }
        int m = (l + r) >> 1;
        build(v, i * 2 + 1, l, m);
        build(v, i * 2 + 2, m + 1, r);
        tree[i].update(tree[i * 2 + 1], tree[i * 2 + 2], l, r);
    }

    template<typename T>
    void build(const vector<T> &v) {
        n = v.size();
        tree.resize(1 << (__lg(max(1, n - 1)) + 2));
        build(v, 0, 0, n - 1);
    }

    item ask(int l, int r, int i, int vl, int vr) {
        if (vl != vr) {
            tree[i].push(tree[i * 2 + 1], tree[i * 2 + 2], vl, vr);
        }
        if (l == vl && r == vr) {
            return tree[i];
        }
        int m = (vl + vr) >> 1;
        if (r <= m) {
            return ask(l, r, i * 2 + 1, vl, m);
        } else if (m < l) {
            return ask(l, r, i * 2 + 2, m + 1, vr);
        } else {
            return item::merge(ask(l, m, i * 2 + 1, vl, m), ask(m + 1, r, i * 2 + 2, m + 1, vr), l, r);
        }
    }

    item ask(int l, int r) {
        l = max(l, 0); r = min(r, n - 1);
        if (l > r) return item();
        return ask(l, r, 0, 0, n - 1);
    }

    template<typename T>
    void set(int ind, const T &t) {
        static array<pair<int, int>, 30> st;
        int l = 0, r = n - 1, i = 0;
        int ptr = -1;
        while (l != r) {
            if (l != r) {
                tree[i].push(tree[i * 2 + 1], tree[i * 2 + 2], l, r);
            }
            st[++ptr] = {l, r};
            int m = (l + r) >> 1;
            if (ind <= m) {
                i = i * 2 + 1;
                r = m;
            } else {
                i = i * 2 + 2;
                l = m + 1;
            }
        }
        tree[i].init(t, l, r);
        while (i != 0) {
            i = (i - 1) / 2;
            tree[i].update(tree[i * 2 + 1], tree[i * 2 + 2], st[ptr].first, st[ptr].second);
            --ptr;
        }
    }

    template<typename Modifier>
    void modify(int l, int r, const Modifier &modifier, int i, int vl, int vr) {
        if (vl != vr) {
            tree[i].push(tree[i * 2 + 1], tree[i * 2 + 2], vl, vr);
        }
        if (l == vl && r == vr) {
            tree[i].modify(modifier, vl, vr);
            return;
        }
        int m = (vl + vr) >> 1;
        if (r <= m) {
            modify(l, r, modifier, i * 2 + 1, vl, m);
        } else if (m < l) {
            modify(l, r, modifier, i * 2 + 2, m + 1, vr);
        } else {
            modify(l, m, modifier, i * 2 + 1, vl, m);
            modify(m + 1, r, modifier, i * 2 + 2, m + 1, vr);
        }
        tree[i].update(tree[i * 2 + 1], tree[i * 2 + 2], vl, vr);
    }

    template<typename Modifier>
    void modify(int l, int r, const Modifier &modifier) {
        l = max(l, 0); r = min(r, n - 1);
        if (l > r) return;
        modify(l, r, modifier, 0, 0, n - 1);
    }

    int get_suf(int i, ll c, ll mx, ll mn, int l, int r) {
        if (l != r) {
            tree[i].push(tree[i * 2 + 1], tree[i * 2 + 2], l, r);
        }
        if (max(mx, tree[i].mx) - min(mn, tree[i].mn) < c) {
            return -1;
        }
        if (l == r)
            return l;
        int m = (l + r) / 2;
        int ind = get_suf(i * 2 + 2, c, mx, mn, m + 1, r);
        if (ind != -1) return ind;
        mx = max(mx, tree[i * 2 + 2].mx);
        mn = min(mn, tree[i * 2 + 2].mn);
        return get_suf(i * 2 + 1, c, mx, mn, l, m);
    }

    int get_suf(ll c) {
        return get_suf(0, c, -1e18, 1e18, 0, n-1);
    }
};

void test_case() {}

struct Q {
    int l, r, v;
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    vector<Q> que;
    for (int i = 0; i < v.size(); ++i) {
        que.pb({l[i], r[i], v[i]});
    }
    que.insert(que.begin(), Q{0, n-1, (int)1e9+100});
    que.insert(que.begin()+1, Q{0, n-1, -(int)1e9-100});

    vector<int> ans(n);

    segtree tree(que.size()); tree.build(vector<int>(que.size(), 0));
    vector<vector<pair<int, int>>> here(n + 1);
    for (int i = 0; i < que.size(); ++i) {
        here[que[i].l].eb(i, que[i].v);
        here[que[i].r + 1].eb(i, -que[i].v);
    }

    for (int i = 0; i < n; ++i) {
        for (auto [ind, v] : here[i])
            tree.modify(ind, tree.n-1, v);

        debug {
            for (int i = 0; i < tree.n; ++i)
                cerr << tree.ask(i, i).mx << " \n"[i + 1 == tree.n];
        }

        int ind = tree.get_suf(c[i]);
        auto it = tree.ask(ind, tree.n-1);
        ll dif = tree.ask(tree.n-1, tree.n-1).mx - tree.ask(ind, ind).mx;
        show(ind, dif, c[i]);
        if (it.imn == ind)
            ans[i] = c[i] + tree.ask(tree.n-1, tree.n-1).mx - tree.ask(it.imx, it.imx).mx;
        else
            ans[i] = 0 + tree.ask(tree.n-1, tree.n-1).mx - tree.ask(it.imn, it.imn).mx;
    }

    return ans;
}

#ifdef HOUSE
int main() {
    int n;
    assert(1 == scanf("%d", &n));
    std::vector<int> c(n);
    for(int i = 0; i < n; ++i) {
        assert(scanf("%d", &c[i]) == 1);
    }

    int q;
    assert(1 == scanf("%d", &q));
    std::vector<int> l(q), r(q), v(q);
    for(int i = 0; i < q; ++i) {
        assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
    }

    std::vector<int> ans = distribute_candies(c, l, r, v);

    for(int i = 0; i < n; ++i) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", ans[i]);
    }
    printf("\n");
    fclose(stdout);
    return 0;
}
#endif

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:241:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  241 |     for (int i = 0; i < v.size(); ++i) {
      |                     ~~^~~~~~~~~~
candies.cpp:251:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Q>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |     for (int i = 0; i < que.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
candies.cpp:267:12: warning: unused variable 'dif' [-Wunused-variable]
  267 |         ll dif = tree.ask(tree.n-1, tree.n-1).mx - tree.ask(ind, ind).mx;
      |            ^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 4 ms 588 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 37840 KB Output is correct
2 Correct 605 ms 41304 KB Output is correct
3 Correct 615 ms 41296 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 288 ms 28352 KB Output is correct
3 Correct 161 ms 7668 KB Output is correct
4 Correct 634 ms 37828 KB Output is correct
5 Correct 614 ms 42452 KB Output is correct
6 Correct 573 ms 42808 KB Output is correct
7 Correct 632 ms 41996 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 136 ms 28888 KB Output is correct
4 Correct 141 ms 7600 KB Output is correct
5 Correct 383 ms 35892 KB Output is correct
6 Correct 360 ms 38584 KB Output is correct
7 Correct 357 ms 38888 KB Output is correct
8 Correct 344 ms 38608 KB Output is correct
9 Correct 422 ms 38968 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 632 ms 37840 KB Output is correct
7 Correct 605 ms 41304 KB Output is correct
8 Correct 615 ms 41296 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 288 ms 28352 KB Output is correct
11 Correct 161 ms 7668 KB Output is correct
12 Correct 634 ms 37828 KB Output is correct
13 Correct 614 ms 42452 KB Output is correct
14 Correct 573 ms 42808 KB Output is correct
15 Correct 632 ms 41996 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 136 ms 28888 KB Output is correct
19 Correct 141 ms 7600 KB Output is correct
20 Correct 383 ms 35892 KB Output is correct
21 Correct 360 ms 38584 KB Output is correct
22 Correct 357 ms 38888 KB Output is correct
23 Correct 344 ms 38608 KB Output is correct
24 Correct 422 ms 38968 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 137 ms 8780 KB Output is correct
27 Correct 296 ms 30884 KB Output is correct
28 Correct 579 ms 40796 KB Output is correct
29 Correct 606 ms 40984 KB Output is correct
30 Correct 586 ms 41212 KB Output is correct
31 Correct 578 ms 41248 KB Output is correct
32 Correct 593 ms 41648 KB Output is correct