제출 #562428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
562428		Lucina	사탕 분배 (IOI21_candies)	C++17	100 / 100	618 ms	44312 KiB

candies

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33