oj.uz

Submission #518336

# Submission time Handle Problem Language Result Execution time Memory
518336 2022-01-23T12:27:33 Z PiejanVDC Distributing Candies (IOI21_candies) C++17
11 / 100
 5000 ms 2097156 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int64_t>>st;

int l,r;
int64_t lim;

int64_t query(int i, int j, int p) {
    if(i > l || j < l)
        assert(0);
    if(i == j) {
        int64_t ans = 0;
        for(auto z : st[p]) {
            if(z > 0) {
                ans += min(z, lim - ans);
            } else ans -= min(-z, ans);
        }
        return ans;
    }
    int mid = (i+j)/2;
    int64_t ans = (i <= l && mid >= l ? query(i,mid,2*p) : query(mid+1,j,2*p+1));
    for(auto z : st[p]) {
        if(z > 0) {
            ans += min(z, lim - ans);
        } else ans -= min(-z, ans);
    }
    return ans;
}

int64_t val;

void update(int i, int j, int p) {
    if(i > r || j < l)
        return;
    if(i >= l && j <= r) {
        int64_t app = val;
        while(!st[p].empty()) {
            if((st[p].back() >= 0 && app >= 0) || (st[p].back() <= 0 && app <= 0))
                app += st[p].back(),st[p].pop_back();
            else break;
        }
        st[p].push_back(app);
        return;
    }
    for(auto z : st[p])
        st[2*p].push_back(z),st[2*p+1].push_back(z);
    st[p].clear();
    int mid = (i+j)/2;
    update(i,mid,2*p),update(mid+1,j,2*p+1);
}

vector<int> distribute_candies(vector<int> c, vector<int> le, vector<int> ri, vector<int> v) {
    const int n = (int)c.size();
    const int q = (int)v.size();
    st.resize(8*n);
    for(int i = 0 ; i < q ; i++) {
        val = v[i];
        l = le[i], r = ri[i];
        update(0, n-1, 1);
    }
    vector<int>ans;
    for(int i = 0 ; i < n ; i++) {
        lim = c[i];
        l = i;
        ans.push_back(query(0,n-1,1));
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 972 KB Output is correct
5 Correct 15 ms 11724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2378 ms 963448 KB Output is correct
2 Correct 2480 ms 960740 KB Output is correct
3 Correct 2401 ms 967056 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1676 ms 801104 KB Output is correct
3 Correct 327 ms 146892 KB Output is correct
4 Runtime error 1591 ms 2097156 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 367 ms 7792 KB Output is correct
4 Correct 409 ms 41312 KB Output is correct
5 Execution timed out 5084 ms 46612 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 972 KB Output is correct
5 Correct 15 ms 11724 KB Output is correct
6 Correct 2378 ms 963448 KB Output is correct
7 Correct 2480 ms 960740 KB Output is correct
8 Correct 2401 ms 967056 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1676 ms 801104 KB Output is correct
11 Correct 327 ms 146892 KB Output is correct
12 Runtime error 1591 ms 2097156 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -