oj.uz

Submission #559046

# Submission time Handle Problem Language Result Execution time Memory
559046 2022-05-09T10:03:43 Z hoanghq2004 Distributing Candies (IOI21_candies) C++17
100 / 100
 388 ms 38340 KB 
#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;
//}

Compilation message

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5140 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 31756 KB Output is correct
2 Correct 328 ms 31704 KB Output is correct
3 Correct 369 ms 31648 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 183 ms 29500 KB Output is correct
3 Correct 65 ms 10988 KB Output is correct
4 Correct 331 ms 37876 KB Output is correct
5 Correct 352 ms 38060 KB Output is correct
6 Correct 361 ms 38340 KB Output is correct
7 Correct 362 ms 37752 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 96 ms 25220 KB Output is correct
4 Correct 69 ms 9072 KB Output is correct
5 Correct 157 ms 31996 KB Output is correct
6 Correct 171 ms 32612 KB Output is correct
7 Correct 183 ms 33308 KB Output is correct
8 Correct 156 ms 31896 KB Output is correct
9 Correct 155 ms 33356 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5140 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct
6 Correct 350 ms 31756 KB Output is correct
7 Correct 328 ms 31704 KB Output is correct
8 Correct 369 ms 31648 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 183 ms 29500 KB Output is correct
11 Correct 65 ms 10988 KB Output is correct
12 Correct 331 ms 37876 KB Output is correct
13 Correct 352 ms 38060 KB Output is correct
14 Correct 361 ms 38340 KB Output is correct
15 Correct 362 ms 37752 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 96 ms 25220 KB Output is correct
19 Correct 69 ms 9072 KB Output is correct
20 Correct 157 ms 31996 KB Output is correct
21 Correct 171 ms 32612 KB Output is correct
22 Correct 183 ms 33308 KB Output is correct
23 Correct 156 ms 31896 KB Output is correct
24 Correct 155 ms 33356 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 67 ms 9096 KB Output is correct
27 Correct 184 ms 29004 KB Output is correct
28 Correct 372 ms 36344 KB Output is correct
29 Correct 339 ms 36592 KB Output is correct
30 Correct 382 ms 36860 KB Output is correct
31 Correct 388 ms 37152 KB Output is correct
32 Correct 323 ms 37248 KB Output is correct