oj.uz

Submission #559043

# Submission time Handle Problem Language Result Execution time Memory
559043 2022-05-09T10:00:38 Z hoanghq2004 Distributing Candies (IOI21_candies) C++17
8 / 100
 408 ms 36600 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(st[1].sum);
        } 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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 4 ms 5000 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 36600 KB Output is correct
2 Correct 328 ms 35780 KB Output is correct
3 Correct 408 ms 35644 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 94 ms 27856 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 4 ms 5000 KB Output isn't correct
3 Halted 0 ms 0 KB -