oj.uz

Submission #1063079

# Submission time Handle Problem Language Result Execution time Memory
1063079 2024-08-17T14:00:27 Z fv3 Distributing Candies (IOI21_candies) C++17
29 / 100
 168 ms 36188 KB 
#include "candies.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int nt = 1;
vector<ll> st_mx, st_mn;

ll get_range_mx(int l, int r, int k, int x, int y)
{
    if (y < l || x > r) return -(1ll << 60);
    if (x >= l && y <= r) return st_mx[k];
    int c = (x + y) / 2;
    return max(get_range_mx(l, r, k*2, x, c), get_range_mx(l, r, k*2|1, c+1, y));
}

ll get_range_mn(int l, int r, int k, int x, int y)
{
    if (y < l || x > r) return 1ll << 60;
    if (x >= l && y <= r) return st_mn[k];
    int c = (x + y) / 2;
    return min(get_range_mn(l, r, k*2, x, c), get_range_mn(l, r, k*2|1, c+1, y));
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    int N = c.size();
    int Q = l.size();

    vector<pair<ll, int>> box(N);
    for (int i = 0; i < N; i++)
        box[i] = {c[i], i};
    sort(box.begin(), box.end());
    reverse(box.begin(), box.end());

    while (nt <= Q) nt <<= 1;
    st_mx = vector<ll>(nt * 2, -(1ll << 60));
    st_mn = vector<ll>(nt * 2, 1ll << 60);

    ll sum = 0;
    map<ll, int> ps_pos;
    for (int i = 0; i < Q; i++)
    {
        sum += v[i];
        st_mx[i + nt + 1] = sum;
        st_mn[i + nt + 1] = sum;
        ps_pos[sum] = i + 1;
    }

    st_mn = st_mx;    for (int i = nt - 1; i >= 1; i--)
        st_mx[i] = max(st_mx[i*2], st_mx[i*2|1]);
    for (int i = nt - 1; i >= 1; i--)
        st_mn[i] = min(st_mn[i*2], st_mn[i*2|1]);

    int time = 0; int score = 0;
    bool minimized = true;
    for (int i = 0; i < Q; i++)
    {
        score += v[i];
        if (score <= 0)
        {
            time = i + 1;
            score = 0;
            minimized = true;
        }
        else if (score >= box[0].first)
        {
            time = i + 1;
            score = box[0].first;
            minimized = false;
        }
    }
    vector<int> res(N);
    res[box[0].second] = score;

    for (int i = 1; i < N; i++)
    {
        while (true)
        {
            ll now = st_mx[nt + time];
            bool ok = false;
            if (minimized)
            {
                ll mx = get_range_mx(time, Q, 1, 0, nt - 1); 
                if (mx - now >= (ll)box[i].first)
                {
                    time = ps_pos[mx];
                    minimized = false;
                    ok = true;
                }
            }
            else
            {
                ll mn = get_range_mn(time, Q, 1, 0, nt - 1); 
                if (box[i].first - (now - mn) <= 0ll)
                {
                    time = ps_pos[mn];
                    minimized = true;
                    ok = true;
                }
            }
            if (!ok) break;
        }
        
        res[box[i].second] = st_mx[nt + Q] - st_mx[nt + time];
        if (!minimized)
            res[box[i].second] += box[i].first;

    }

    return res;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 129 ms 28256 KB Output is correct
4 Correct 63 ms 7248 KB Output is correct
5 Correct 143 ms 26092 KB Output is correct
6 Correct 168 ms 35496 KB Output is correct
7 Correct 160 ms 36000 KB Output is correct
8 Correct 128 ms 24100 KB Output is correct
9 Correct 135 ms 36072 KB Output is correct

Subtask #5
0 / 33.0

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