oj.uz

Submission #518330

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

vector<vector<int>>st;

int l,r;
int lim;

int query(int i, int j, int p) {
    if(i > l || j < l)
        assert(0);
    if(i == j) {
        int 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;
    int 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;
}

int val;

void update(int i, int j, int p) {
    if(i > r || j < l)
        return;
    if(i >= l && j <= r) {
        while(!st[p].empty()) {
            if((st[p].back() >= 0 && val >= 0) || st[p].back() <= 0 && val <= 0)
                val += st[p].back(),st[p].pop_back();
            else break;
        }
        st[p].push_back(val);
        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;
}

Compilation message

candies.cpp: In function 'void update(int, int, int)':
candies.cpp:39:69: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   39 |             if((st[p].back() >= 0 && val >= 0) || st[p].back() <= 0 && val <= 0)
      |                                                   ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 2245 ms 2097156 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Incorrect 1206 ms 425584 KB Output isn't correct
3 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 397 ms 7384 KB Output is correct
4 Correct 410 ms 41880 KB Output is correct
5 Execution timed out 5071 ms 46140 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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