oj.uz

Submission #493075

# Submission time Handle Problem Language Result Execution time Memory
493075 2021-12-10T04:40:07 Z qwerasdfzxcl Distributing Candies (IOI21_candies) C++17
100 / 100
 714 ms 47240 KB 
#include "candies.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const ll INF = 1e18;
struct Seg{
    pair<ll, ll> tree[800800];
    ll lazy[800800];
    pair<ll, ll> combine(pair<ll, ll> x, pair<ll, ll> y){
        return pair<ll, ll>(max(x.first, y.first), min(x.second, y.second));
    }
    void propagate(int i, int l, int r){
        tree[i].first += lazy[i];
        tree[i].second += lazy[i];
        if (l!=r) lazy[i<<1] += lazy[i], lazy[i<<1|1] += lazy[i];
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, ll x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] += x;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, x);
        update(i<<1|1, m+1, r, s, e, x);
        tree[i] = combine(tree[i<<1], tree[i<<1|1]);
    }
    pair<ll, ll> query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if (r<s || e<l) return {-INF, INF};
        if (s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return combine(query(i<<1, l, m, s, e), query(i<<1|1, m+1, r, s, e));
    }
    int left_bound(int i, int l, int r, int x, pair<ll, ll> cur){
        propagate(i, l, r);
        assert(cur.first-cur.second<=x);
        auto p = combine(cur, tree[i]);
        if (p.first-p.second<=x) return -1;
        if (l==r) return l;

        int m = (l+r)>>1;
        int tmp = left_bound(i<<1|1, m+1, r, x, cur);
        if (tmp!=-1) return tmp;
        return left_bound(i<<1, l, m, x, combine(cur, tree[i<<1|1]));
    }
}tree;
vector<int> qb[200200], qe[200200];

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    int q = v.size();
    vector<int> ret(n);
    for (int i=0;i<q;i++){
        qb[l[i]+1].push_back(i+1);
        qe[r[i]+1].push_back(i+1);
    }

    for (int i=1;i<=n;i++){
        for (auto &x:qe[i-1]) tree.update(1, 0, q, x, q, -v[x-1]);
        for (auto &x:qb[i]) tree.update(1, 0, q, x, q, v[x-1]);

        int idx = tree.left_bound(1, 0, q, c[i-1], {-INF, INF});
        //printf("%d: %d %lld %lld\n", i, idx, tree.tree[1].first, tree.tree[1].second);
        if (idx==-1) ret[i-1] = tree.query(1, 0, q, q, q).first - tree.query(1, 0, q, 0, q).second;
        else{
            ll tmp = tree.query(1, 0, q, idx, idx).first;
            auto p = tree.query(1, 0, q, idx, q);
            if (tmp==p.first) ret[i-1] = tree.query(1, 0, q, q, q).first - p.second;
            else if (tmp==p.second) ret[i-1] = c[i-1] - p.first + tree.query(1, 0, q, q, q).first;
            else exit(1);
        }
    }

    return ret;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 22220 KB Output is correct
2 Correct 9 ms 22240 KB Output is correct
3 Correct 11 ms 22244 KB Output is correct
4 Correct 11 ms 22364 KB Output is correct
5 Correct 13 ms 22380 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 40548 KB Output is correct
2 Correct 621 ms 44652 KB Output is correct
3 Correct 595 ms 44484 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22220 KB Output is correct
2 Correct 246 ms 33908 KB Output is correct
3 Correct 153 ms 27996 KB Output is correct
4 Correct 542 ms 46532 KB Output is correct
5 Correct 601 ms 46948 KB Output is correct
6 Correct 559 ms 47240 KB Output is correct
7 Correct 631 ms 46616 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22220 KB Output is correct
2 Correct 11 ms 22220 KB Output is correct
3 Correct 119 ms 32696 KB Output is correct
4 Correct 141 ms 24800 KB Output is correct
5 Correct 288 ms 35168 KB Output is correct
6 Correct 296 ms 35188 KB Output is correct
7 Correct 320 ms 35248 KB Output is correct
8 Correct 308 ms 38520 KB Output is correct
9 Correct 313 ms 40080 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 22220 KB Output is correct
2 Correct 9 ms 22240 KB Output is correct
3 Correct 11 ms 22244 KB Output is correct
4 Correct 11 ms 22364 KB Output is correct
5 Correct 13 ms 22380 KB Output is correct
6 Correct 615 ms 40548 KB Output is correct
7 Correct 621 ms 44652 KB Output is correct
8 Correct 595 ms 44484 KB Output is correct
9 Correct 12 ms 22220 KB Output is correct
10 Correct 246 ms 33908 KB Output is correct
11 Correct 153 ms 27996 KB Output is correct
12 Correct 542 ms 46532 KB Output is correct
13 Correct 601 ms 46948 KB Output is correct
14 Correct 559 ms 47240 KB Output is correct
15 Correct 631 ms 46616 KB Output is correct
16 Correct 11 ms 22220 KB Output is correct
17 Correct 11 ms 22220 KB Output is correct
18 Correct 119 ms 32696 KB Output is correct
19 Correct 141 ms 24800 KB Output is correct
20 Correct 288 ms 35168 KB Output is correct
21 Correct 296 ms 35188 KB Output is correct
22 Correct 320 ms 35248 KB Output is correct
23 Correct 308 ms 38520 KB Output is correct
24 Correct 313 ms 40080 KB Output is correct
25 Correct 14 ms 22132 KB Output is correct
26 Correct 123 ms 25984 KB Output is correct
27 Correct 245 ms 36512 KB Output is correct
28 Correct 573 ms 45128 KB Output is correct
29 Correct 638 ms 45516 KB Output is correct
30 Correct 637 ms 45716 KB Output is correct
31 Correct 639 ms 45916 KB Output is correct
32 Correct 714 ms 46112 KB Output is correct