제출 #559046

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

candies

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "candies.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 10;

vector <pair <int, int> > s[N];

struct node {
    long long maxi, mini, sum;
} st[N * 4];

void add(int id, int L, int R, int i, int val) {
//    cout << i << ' ' << val << "aaa\n";
    if (L == R) {
        st[id].maxi = max(val, 0);
        st[id].mini = min(val, 0);
        st[id].sum = val;
        return;
    }
    int mid = L + R >> 1;
    if (i <= mid) add(id * 2, L, mid, i, val);
    else add(id * 2 + 1, mid + 1, R, i, val);
    st[id].maxi = max(st[id * 2 + 1].maxi, st[id * 2 + 1].sum + st[id * 2].maxi);
    st[id].mini = min(st[id * 2 + 1].mini, st[id * 2 + 1].sum + st[id * 2].mini);
    st[id].sum = st[id * 2].sum + st[id * 2 + 1].sum;
}

tuple <long long, long long, long long, int> get(int id, int L, int R, int k, long long maxi, long long mini, long long sum) {
    if (L == R) return make_tuple(max(maxi, st[id].maxi + sum), min(mini, st[id].mini + sum), sum, L);
    int mid = L + R >> 1;
    long long _maxi = max(maxi, st[id * 2 + 1].maxi + sum);
    long long _mini = min(mini, st[id * 2 + 1].mini + sum);
    long long _sum = sum + st[id * 2 + 1].sum;
//    cout << _maxi - _mini << "aaa\n";
    if (_maxi - _mini > k) return get(id * 2 + 1, mid + 1, R, k, maxi, mini, sum);
    else return get(id * 2, L, mid, k, _maxi, _mini, _sum);
}


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();
    for (int i = 0; i < q; ++i) {
        s[l[i]].push_back({v[i], i});
        s[r[i] + 1].push_back({v[i], i + q});
    }
    vector <int> ans;
    for (int i = 0; i < n; ++i) {
        for (auto [x, id]: s[i]) {
            if (id < q) add(1, 0, q - 1, id, x);
            else add(1, 0, q - 1, id - q, 0);
//            cout << id << ' ' << x << ' ' << st[1].sum << "aaaa\n";
//            cout << x << ' ' << id << "aa\n";
        }
//        cout << st[1].sum << "-----\n";
        auto [maxi, mini, sum, id] = get(1, 0, q - 1, c[i], 0, 0, 0);
//        cout << maxi << ' ' << mini << " " << sum << "aa\n";
//        cout << id << "aa\n";
        if (maxi - mini <= c[i]) {
            ans.push_back(maxi);
        } else {
            if (v[id] < 0) {
                ans.push_back(maxi);
            } else {
                ans.push_back(c[i] + mini);
            }
        }
    }
    return ans;
}
//
//
//int main() {
//    int n;
//    assert(1 == scanf("%d", &n));
//    std::vector<int> c(n);
//    for(int i = 0; i < n; ++i) {
//        assert(scanf("%d", &c[i]) == 1);
//    }
//
//    int q;
//    assert(1 == scanf("%d", &q));
//    std::vector<int> l(q), r(q), v(q);
//    for(int i = 0; i < q; ++i) {
//        assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
//    }
//
//    std::vector<int> ans = distribute_candies(c, l, r, v);
//
//    for(int i = 0; i < n; ++i) {
//        if (i > 0) {
//            printf(" ");
//        }
//        printf("%d", ans[i]);
//    }
//    printf("\n");
//    fclose(stdout);
//    return 0;
//}

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

candies.cpp: In function 'void add(int, int, int, int, int)':
candies.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mid = L + R >> 1;
      |               ~~^~~
candies.cpp: In function 'std::tuple<long long int, long long int, long long int, int> get(int, int, int, int, long long int, long long int, long long int)':
candies.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     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