oj.uz

Submission #562428

# Submission time Handle Problem Language Result Execution time Memory
562428 2022-05-14T10:27:52 Z Lucina Distributing Candies (IOI21_candies) C++17
100 / 100
 618 ms 44312 KB 
#include "candies.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int nax = 2e5 + 10;
int n, q;
const int64_t INF = 1e15;
struct seg_node {
    int64_t mn, mx;
    int min_ind, max_ind;
    seg_node() :mn(INF), mx(-INF) {}
    seg_node(int64_t x, int id): mn(x), mx(x), min_ind(id), max_ind(id){}
    inline int64_t dif() {return mx - mn;}
    inline void apply(int64_t x) {
        mn += x;
        mx += x;
    }
};

int64_t bit[nax];
void update(int idx, int64_t val) {
    for (; idx <= q  ; idx += idx & -idx) bit[idx] += val;
}
int64_t get_sum(int idx) {
    int64_t res = 0;
    for (; idx > 0; idx -= idx & -idx) res += bit[idx];
    return res;
}

seg_node operator +(const seg_node &a, const seg_node &b) {
    seg_node res;
    res.min_ind = a.mn < b.mn ? (res.mn = a.mn, a.min_ind) : (res.mn = b.mn, b.min_ind);
    res.max_ind = a.mx > b.mx ? (res.mx = a.mx, a.max_ind) : (res.mx = b.mx, b.max_ind);
    return res;
}

seg_node sg[nax << 2];
int64_t tag[nax << 2];

void push(int v) {
    if (!tag[v]) return;
    sg[v << 1].apply(tag[v]);
    sg[v << 1 | 1].apply(tag[v]);
    tag[v << 1] += tag[v];
    tag[v << 1 | 1] += tag[v];
    tag[v] = 0;
}
void range_add(int v, int x, int y, int l, int r, int64_t add) {
    if (x != y) push(v);
    if (l == x && r == y) {
        tag[v] += add;
        sg[v].apply(add);
        if (x != y) push(v);
        return;
    }
    int mid = x + y >> 1;
    if (r <= mid) range_add(v << 1, x, mid, l, r, add);
    else if (l > mid) range_add(v * 2 + 1, mid + 1, y, l, r, add);
    else range_add(v << 1, x, mid, l, mid, add), range_add(v * 2 + 1, mid + 1, y, mid + 1, r, add);
    sg[v] = sg[v << 1] + sg[v << 1 | 1];
}

/// find maximum index such that
/// max(index, q) - min(index, q) >= k

int find_last(int v, int l, int r, int tar, seg_node &info) {
    if (l == r) return (info + sg[v]).dif() >= tar ? l : -1;
    push(v);
    if ((info + sg[v]).dif() < tar) return -1;
    int mid = l + r >> 1;
    seg_node info_right = info + sg[v << 1 | 1];
    if (info_right.dif() >= tar) return find_last(v << 1 | 1, mid + 1, r, tar, info);
    info = info_right;
    return find_last(v << 1, l, mid, tar, info);
}

void build(int v, int l, int r) {
    if (l == r) {
        sg[v] = seg_node(0, l);
    } else {
        int mid = l + r >> 1;
        build(v << 1, l, mid);
        build(v << 1 | 1, mid + 1, r);
        sg[v] = sg[v << 1] + sg[v << 1 | 1];
    }
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {

    n = c.size();
    q = v.size();

    vector <vector <pair <int, int>>> sc(n + 1);

    for (int i = 0 ; i < q ; ++ i) {
        sc[l[i]].emplace_back(i + 1, v[i]);
        sc[r[i] + 1].emplace_back(i + 1, -v[i]);
    }


    build(1, 0, q);
    vector <int> ans(n);
    int64_t all_sum = 0;

    for (int s = 0 ; s < n ; ++ s) {
        int k = c[s];
        for (auto &[idx, val] : sc[s]) {
            update(idx, val);
            all_sum += val;
            range_add(1, 0, q, idx, q, val);
        }
        seg_node info;
        int ans1 = find_last(1, 0, q, k, info);

        if (ans1 == -1) {
            int min_ind = sg[1].min_ind;
            ans[s] = all_sum - get_sum(min_ind);
        } else {
            int64_t cur_val = get_sum(ans1);
            int lst_ind;
            if (cur_val < info.mx) lst_ind = info.max_ind;
            else lst_ind = info.min_ind;
            int64_t res = lst_ind == q ? 0 : all_sum - get_sum(lst_ind);
            if (cur_val < info.mx) ans[s] = k + res;
            else ans[s] = res;
        }
    }
    return ans;
}

Compilation message

candies.cpp: In function 'void range_add(int, int, int, int, int, int64_t)':
candies.cpp:57:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid = x + y >> 1;
      |               ~~^~~
candies.cpp: In function 'int find_last(int, int, int, int, seg_node&)':
candies.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int mid = l + r >> 1;
      |               ~~^~~
candies.cpp: In function 'void build(int, int, int)':
candies.cpp:82:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19028 KB Output is correct
2 Correct 8 ms 19104 KB Output is correct
3 Correct 11 ms 19284 KB Output is correct
4 Correct 11 ms 19240 KB Output is correct
5 Correct 12 ms 19340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 44312 KB Output is correct
2 Correct 478 ms 43920 KB Output is correct
3 Correct 515 ms 43972 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19028 KB Output is correct
2 Correct 359 ms 34448 KB Output is correct
3 Correct 82 ms 26788 KB Output is correct
4 Correct 618 ms 43956 KB Output is correct
5 Correct 539 ms 43912 KB Output is correct
6 Correct 573 ms 43896 KB Output is correct
7 Correct 502 ms 43996 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19028 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 139 ms 33644 KB Output is correct
4 Correct 68 ms 26652 KB Output is correct
5 Correct 212 ms 39956 KB Output is correct
6 Correct 208 ms 40080 KB Output is correct
7 Correct 207 ms 39812 KB Output is correct
8 Correct 194 ms 39964 KB Output is correct
9 Correct 216 ms 39956 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19028 KB Output is correct
2 Correct 8 ms 19104 KB Output is correct
3 Correct 11 ms 19284 KB Output is correct
4 Correct 11 ms 19240 KB Output is correct
5 Correct 12 ms 19340 KB Output is correct
6 Correct 506 ms 44312 KB Output is correct
7 Correct 478 ms 43920 KB Output is correct
8 Correct 515 ms 43972 KB Output is correct
9 Correct 8 ms 19028 KB Output is correct
10 Correct 359 ms 34448 KB Output is correct
11 Correct 82 ms 26788 KB Output is correct
12 Correct 618 ms 43956 KB Output is correct
13 Correct 539 ms 43912 KB Output is correct
14 Correct 573 ms 43896 KB Output is correct
15 Correct 502 ms 43996 KB Output is correct
16 Correct 8 ms 19028 KB Output is correct
17 Correct 9 ms 19028 KB Output is correct
18 Correct 139 ms 33644 KB Output is correct
19 Correct 68 ms 26652 KB Output is correct
20 Correct 212 ms 39956 KB Output is correct
21 Correct 208 ms 40080 KB Output is correct
22 Correct 207 ms 39812 KB Output is correct
23 Correct 194 ms 39964 KB Output is correct
24 Correct 216 ms 39956 KB Output is correct
25 Correct 8 ms 19104 KB Output is correct
26 Correct 65 ms 26700 KB Output is correct
27 Correct 349 ms 34272 KB Output is correct
28 Correct 501 ms 43968 KB Output is correct
29 Correct 515 ms 43908 KB Output is correct
30 Correct 547 ms 43856 KB Output is correct
31 Correct 552 ms 43912 KB Output is correct
32 Correct 584 ms 43920 KB Output is correct