oj.uz

Submission #437978

# Submission time Handle Problem Language Result Execution time Memory
437978 2021-06-27T11:22:58 Z CyanForces Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 36388 KB 
#include "candies.h"

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define debug(...) //ignore
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long double ld;

struct T {
    ll sum = 0;
    ll max_pre = 0;
    ll min_pre = 0;
};
constexpr T unit;

T from_int(ll t) {
    T res;
    res.sum = t;
    res.max_pre = max<ll>(t,0);
    res.min_pre = min<ll>(t,0);
    return res;
};

T f(T a, T b) {
    T res;
    res.sum = a.sum + b.sum;
    res.max_pre = max(a.max_pre, a.sum + b.max_pre);
    res.min_pre = min(a.min_pre, a.sum + b.min_pre);
    return res;
}

struct Tree {
    vector<T> s; int n;
    Tree(int n_ = 0, T def = unit) {
        n = 1;
        while(n < n_) n*=2;
        s.assign(2*n, def);
    }

    void update(int pos, T val) {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e) { // query [b, e)
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
        std::vector<int> r, std::vector<int> v) {
    int n = sz(c);
    int q = sz(l);
    vi s(n);

    vector<vi> at_l(n+1), at_r(n+1);
    rep(i,0,q) {
        at_l[l[i]].emplace_back(i);
        at_r[r[i]+1].emplace_back(i);
    }

    int Q = q+10;
    Tree segtree(Q);
    segtree.update(0,from_int(1e18));
    segtree.update(1,from_int(-1e18));

    rep(i,0,n) {
        for(int qi : at_l[i]) segtree.update(qi+10, from_int(v[qi])); // activate
        for(int qi : at_r[i]) segtree.update(qi+10, unit); // deactivate
        debug()

        segtree.update(2, from_int(0));
        ll cap = c[i];
        int t = Q;
        T v = segtree.query(t,Q);
        while(v.max_pre - v.min_pre < cap) {
            debug(v);
            --t;
            v = segtree.query(t,Q);
        }
        debug(v);
        T vv = segtree.query(t+1,Q);
        ll ans = 0;
        if(vv.sum > v.sum) {
            ans = v.sum - v.min_pre;
        }
        else if(vv.sum < v.sum) {
            ans = v.sum - v.max_pre + c[i];
        }
        else assert(false);
        s[i] = ans;
    }

    return s;
}

Subtask #1
3.0 / 3.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 2 ms 460 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 32 ms 588 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5029 ms 36388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Execution timed out 5032 ms 20188 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Execution timed out 5090 ms 19148 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.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 2 ms 460 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 32 ms 588 KB Output is correct
6 Execution timed out 5029 ms 36388 KB Time limit exceeded
7 Halted 0 ms 0 KB -