oj.uz

Submission #444392

# Submission time Handle Problem Language Result Execution time Memory
444392 2021-07-14T00:26:45 Z JvThunder Distributing Candies (IOI21_candies) C++17
100 / 100
 1388 ms 48372 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
const int MAXQ = 1000005;
const ll INF = (ll)(1e18);
 
struct SegmentTree 
{
    int n;
    ll vmin[MAXQ] = {0};
    ll vmax[MAXQ] = {0};
    ll lazy[MAXQ] = {0};
 
    void init(int _n) { n = _n; }
 
    void lazy_update(int node, int from, int to)
    {
        vmin[node] += lazy[node]; vmax[node] += lazy[node];
        if (from < to) 
        {
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node];
        }
        lazy[node] = 0;
    }
 
    void update(int node, int from, int to, int L, int R, int add)
    {
        lazy_update(node, from, to);
        if (from > R || to < L) return;
        if (L <= from && to <= R) {
            lazy[node] += add;
            lazy_update(node, from, to);
            return;
        }
        int mid = (from + to) / 2;
        update(node * 2, from, mid, L, R, add);
        update(node * 2 + 1, mid + 1, to, L, R, add);
        vmin[node] = min(vmin[node * 2], vmin[node * 2 + 1]);
        vmax[node] = max(vmax[node * 2], vmax[node * 2 + 1]);
    }
 
    ll get(int node, int from, int to, int lb) 
    {
        lazy_update(node, from, to);
        if (from == to) return vmin[node];
        int mid = (from + to) / 2;
        if (vmax[node * 2 + 1] + lazy[node * 2 + 1] >= lb)
            return get(node * 2 + 1, mid + 1, to, lb);
        return min( vmin[node * 2 + 1] + lazy[node * 2 + 1], get(node * 2, from, mid, lb) );
    }
 
    void add_range(int L, int R, int add) 
    {
        update(1, 0, n - 1, L, R, add);
    }
 
    ll min_suffix(int lb) 
    {
        if (vmax[1] < lb) return -INF;
        return min(0LL, get(1, 0, n - 1, lb));
    }
} T;
 
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<int> A(n);
    
    vector<vector<int>> begin_at(n,vector<int>()), end_at(n,vector<int>());
    for(int i=0;i<q;i++) 
    {
        begin_at[L[i]].push_back(i);
        end_at[R[i]].push_back(i);
    }
 
    T.init(q+1);
    vector<int> final_A(n);
    for(int i=0;i<n;i++)
    {
        if (i>0) 
        {
            T.add_range(0,0,-A[i-1]);
            for(int j:end_at[i-1]) T.add_range(0,1+j,-V[j]);
        }
        T.add_range(0,0,A[i]);
        for(int j : begin_at[i]) T.add_range(0,1+j,V[j]);
 
        int l = 1, r = C[i] + 1;
        while (l <= r) 
        {
            int mid = (l + r) / 2;
            ll smin = T.min_suffix(mid);
            if (-smin + mid > C[i]) r = mid - 1;
            else l = mid + 1;
        }
        final_A[i] = r;
    }

    return final_A;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 12 ms 23668 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 14 ms 23756 KB Output is correct
5 Correct 17 ms 24012 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1113 ms 48372 KB Output is correct
2 Correct 1174 ms 48212 KB Output is correct
3 Correct 1174 ms 48192 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 378 ms 31444 KB Output is correct
3 Correct 517 ms 36472 KB Output is correct
4 Correct 1388 ms 48196 KB Output is correct
5 Correct 1338 ms 48236 KB Output is correct
6 Correct 1388 ms 48196 KB Output is correct
7 Correct 811 ms 48200 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 152 ms 30388 KB Output is correct
4 Correct 267 ms 36340 KB Output is correct
5 Correct 559 ms 42836 KB Output is correct
6 Correct 598 ms 42808 KB Output is correct
7 Correct 706 ms 42808 KB Output is correct
8 Correct 538 ms 42808 KB Output is correct
9 Correct 1075 ms 42928 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 12 ms 23668 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 14 ms 23756 KB Output is correct
5 Correct 17 ms 24012 KB Output is correct
6 Correct 1113 ms 48372 KB Output is correct
7 Correct 1174 ms 48212 KB Output is correct
8 Correct 1174 ms 48192 KB Output is correct
9 Correct 12 ms 23756 KB Output is correct
10 Correct 378 ms 31444 KB Output is correct
11 Correct 517 ms 36472 KB Output is correct
12 Correct 1388 ms 48196 KB Output is correct
13 Correct 1338 ms 48236 KB Output is correct
14 Correct 1388 ms 48196 KB Output is correct
15 Correct 811 ms 48200 KB Output is correct
16 Correct 12 ms 23756 KB Output is correct
17 Correct 13 ms 23756 KB Output is correct
18 Correct 152 ms 30388 KB Output is correct
19 Correct 267 ms 36340 KB Output is correct
20 Correct 559 ms 42836 KB Output is correct
21 Correct 598 ms 42808 KB Output is correct
22 Correct 706 ms 42808 KB Output is correct
23 Correct 538 ms 42808 KB Output is correct
24 Correct 1075 ms 42928 KB Output is correct
25 Correct 12 ms 23732 KB Output is correct
26 Correct 244 ms 36456 KB Output is correct
27 Correct 355 ms 31388 KB Output is correct
28 Correct 935 ms 48236 KB Output is correct
29 Correct 985 ms 48196 KB Output is correct
30 Correct 1006 ms 48248 KB Output is correct
31 Correct 1046 ms 48188 KB Output is correct
32 Correct 1112 ms 48280 KB Output is correct