oj.uz

Submission #493061

# Submission time Handle Problem Language Result Execution time Memory
493061 2021-12-10T04:15:50 Z qwerasdfzxcl Distributing Candies (IOI21_candies) C++17
0 / 100
 512 ms 40676 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);
        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{
            int 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 assert(0);
        }
    }

    return ret;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22220 KB Output is correct
2 Correct 11 ms 22220 KB Output is correct
3 Correct 113 ms 32736 KB Output is correct
4 Correct 125 ms 24692 KB Output is correct
5 Correct 278 ms 35192 KB Output is correct
6 Correct 294 ms 35068 KB Output is correct
7 Incorrect 295 ms 35292 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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