oj.uz

답안 #494116

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
494116 2021-12-14T11:52:05 Z maksim1744 사탕 분배 (IOI21_candies) C++17
100 / 100
 642 ms 37964 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);

        int ind = tree.get_suf(c[i]);
        auto it = tree.ask(ind, tree.n-1);
        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) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 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 3 ms 460 KB Output is correct
5 Correct 5 ms 588 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 559 ms 37848 KB Output is correct
2 Correct 581 ms 37964 KB Output is correct
3 Correct 642 ms 37840 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 292 ms 28324 KB Output is correct
3 Correct 166 ms 7664 KB Output is correct
4 Correct 560 ms 37836 KB Output is correct
5 Correct 630 ms 37796 KB Output is correct
6 Correct 603 ms 37840 KB Output is correct
7 Correct 567 ms 37840 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 131 ms 28728 KB Output is correct
4 Correct 111 ms 7608 KB Output is correct
5 Correct 357 ms 35916 KB Output is correct
6 Correct 329 ms 35808 KB Output is correct
7 Correct 347 ms 35804 KB Output is correct
8 Correct 318 ms 35748 KB Output is correct
9 Correct 378 ms 35808 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 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 3 ms 460 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 559 ms 37848 KB Output is correct
7 Correct 581 ms 37964 KB Output is correct
8 Correct 642 ms 37840 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 292 ms 28324 KB Output is correct
11 Correct 166 ms 7664 KB Output is correct
12 Correct 560 ms 37836 KB Output is correct
13 Correct 630 ms 37796 KB Output is correct
14 Correct 603 ms 37840 KB Output is correct
15 Correct 567 ms 37840 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 131 ms 28728 KB Output is correct
19 Correct 111 ms 7608 KB Output is correct
20 Correct 357 ms 35916 KB Output is correct
21 Correct 329 ms 35808 KB Output is correct
22 Correct 347 ms 35804 KB Output is correct
23 Correct 318 ms 35748 KB Output is correct
24 Correct 378 ms 35808 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 117 ms 7604 KB Output is correct
27 Correct 280 ms 28284 KB Output is correct
28 Correct 577 ms 37852 KB Output is correct
29 Correct 559 ms 37848 KB Output is correct
30 Correct 640 ms 37840 KB Output is correct
31 Correct 534 ms 37720 KB Output is correct
32 Correct 583 ms 37832 KB Output is correct