oj.uz

답안 #582062

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
582062 2022-06-23T10:45:01 Z georgievskiy 사탕 분배 (IOI21_candies) C++17
0 / 100
 1381 ms 42568 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 2e5;
//const int N = 1000;
const ll inf = 2e18;


struct ST {
    ll t[4 * N], mn[4 * N], mx[4 * N];
    ll q;
    ST(){
        fill(t, t + 4 * N, 0);
        fill(mn, mn + 4 * N, 0);
        fill(mx, mx + 4 * N, 0);
    }

    inline void push(int v) {
        t[2 * v + 1] += t[v], mn[2 * v + 1] += t[v], mx[2 * v + 1] += t[v];
        t[2 * v + 2] += t[v], mn[2 * v + 2] += t[v], mx[2 * v + 2] += t[v];
        t[v] = 0;
    }
    inline void upd(int v) {
        mn[v] = min(mn[2 * v + 1], mn[2 * v + 2]), mx[v] = max(mx[2 * v + 1], mx[2 * v + 2]);
    }

    void add(int v, int tl, int tr, int l, int r, ll d) {
        if (tl >= r || tr <= l)
            return;
        if (tl >= l && tr <= r) {
            t[v] += d, mn[v] += d, mx[v] += d;
            return;
        }
        push(v);
        int m = (tl + tr) / 2;
        add(2 * v + 1, tl, m, l, r, d);
        add(2 * v + 2, m, tr, l, r, d);
        upd(v);
    }

    ll get_min(int v, int tl, int tr, int l, int r) {
        if (tl >= r || tr <= l)
            return inf;
        if (tl >= l && tr <= r)
            return mn[v];
        push(v);
        int m = (tl + tr) / 2;
        ll ans = min(get_min(2 * v + 1, tl, m, l, r), get_min(2 * v + 2, m, tr, l, r));
        upd(v);
        return ans;
    }

    ll get_max(int v, int tl, int tr, int l, int r) {
        if (tl >= r || tr <= l)
            return -inf;
        if (tl >= l && tr <= r)
            return mx[v];
        push(v);
        int m = (tl + tr) / 2;
        ll ans = max(get_max(2 * v + 1, tl, m, l, r), get_max(2 * v + 2, m, tr, l, r));
        upd(v);
        return ans;
    }

    ll get_val(int v, int tl, int tr, int i) {
        if (i < tl || i >= tr)
            return 0;
        if (tl + 1 == tr)
            return t[v];
        push(v);
        int m = (tl + tr) / 2;
        ll ans;
        if (i < m)
            ans = get_val(2 * v + 1, tl, m, i);
        else
            ans = get_val(2 * v + 2, m, tr, i);
        upd(v);
        return ans;
    }

    ll get_min(int left) {
        return get_min(0, 0, q, left+1, q);
    }

    ll get_max(int left) {
        return get_max(0, 0, q, left+1, q);
    }

    ll get_val(int ind) {
        return get_val(0, 0, q, ind+1);
    }

    ll get_range(int left) {
        return get_max(left) - get_min(left);
    }
    void add(int left, int right, ll d) {
        add(0, 0, q, left + 1, right + 1, d);
    }
};

vector<pair<int, int>> ev[2 * N];

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

    ST st;
    st.q = q+1;
    vector<int> ans(n);

    for (int i = 0; i < n; i++) {
        for (auto p : ev[i])
            st.add(p.first, q, p.second);

        ll range = st.get_range(-1);
        if (range <= c[i]) {
            ans[i] = st.get_val(q) - st.get_min(-1);
            continue;
        }

        int l = -1, r = q;
        while (r - l > 1) {
            int mid = (r + l) / 2;
            if (st.get_range(mid) > c[i])
                l = mid;
            else
                r = mid;
        }

        ll left_val = st.get_val(l), last_val = st.get_val(q-1);
        if (left_val > last_val) {
            ans[i] = last_val - st.get_min(l);
        } else {
            ans[i] = c[i] - st.get_max(l) + last_val;
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28372 KB Output is correct
2 Incorrect 17 ms 28464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1381 ms 42568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 28500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 28372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28372 KB Output is correct
2 Incorrect 17 ms 28464 KB Output isn't correct
3 Halted 0 ms 0 KB -