oj.uz

Submission #1069376

# Submission time Handle Problem Language Result Execution time Memory
1069376 2024-08-21T20:43:15 Z Boas Distributing Candies (IOI21_candies) C++17
29 / 100
 111 ms 27480 KB 
#include "candies.h"

#pragma GCC optimize("trapv")

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<int> vi;
typedef vector<signed> vi32;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef set<int> si;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)x - 1; i >= 0; i--)
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define sz(x) (int)x.size()

vi32 distribute_candies(vi32 c, vi32 l, vi32 r, vi32 v)
{
    int n = sz(c);
    int q = sz(l);

    vi32 s(n);
    vi sufSum(q + 1);
    vi sufMax(q + 1);
    vi sufMin(q + 1);
    vi diff(q + 1);
    // map<int,int> lastIx;
    rev(q, j)
    {
        assert(n - 1 == r[j]);
        sufSum[j] = sufSum[j + 1] + v[j];
        sufMin[j] = min(sufMin[j + 1], sufSum[j]);
        sufMax[j] = max(sufMax[j + 1], sufSum[j]);
        diff[j] = sufMax[j] - sufMin[j];
    }
    loop(n, i)
    {
        int ix = q - (lower_bound(RALL(diff), c[i]) - diff.rbegin());
        if (ix == -1)
        {
            s[i] = sufMax[0];
            assert(s[i] >= 0);
            assert(s[i] <= c[i]);
            continue;
        }
        if (sufSum[ix] == sufMax[ix])
        {
            int mn = sufMin[ix];
            int mnIx = upper_bound(ALL(sufMin), mn) - sufMin.begin() - 1;
            s[i] = c[i] + sufSum[mnIx];
            assert(s[i] >= 0);
        }
        else
        {
            int mx = sufMax[ix];
            int mxIx = q - (lower_bound(RALL(sufMax), mx) - sufMax.rbegin());
            s[i] = sufSum[mxIx];
            assert(s[i] >= 0);
        }
    }
    return s;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 27480 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 37 ms 11344 KB Output is correct
4 Correct 44 ms 4080 KB Output is correct
5 Correct 88 ms 17256 KB Output is correct
6 Correct 86 ms 17744 KB Output is correct
7 Correct 111 ms 18480 KB Output is correct
8 Correct 86 ms 17168 KB Output is correct
9 Correct 103 ms 18512 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -