oj.uz

Submission #1063004

# Submission time Handle Problem Language Result Execution time Memory
1063004 2024-08-17T13:12:50 Z fv3 Distributing Candies (IOI21_candies) C++17
0 / 100
 147 ms 36200 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 0;
    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);
    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++)
    {
        if (minimized)
        {
            ll mx = get_range_mx(time, Q, 1, 0, nt - 1); 
            if (mx - st_mx[nt + time] >= (ll)box[i].first)
            {
                time = ps_pos[mx];
                minimized = false;
            }
        }
        else
        {
            ll mn = get_range_mn(time, Q, 1, 0, nt - 1); 
            if (box[i].first - (st_mn[nt + time] - mn) <= 0ll)
            {
                time = ps_pos[mn];
                minimized = true;
            }
        }
        //cerr << st_mx[nt + Q] << " - " << st_mx[nt + time] << '\n';

        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 348 KB Output is correct
2 Incorrect 1 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 147 ms 36200 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
0 / 29.0

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

Subtask #5
0 / 33.0

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