oj.uz

Submission #467097

# Submission time Handle Problem Language Result Execution time Memory
467097 2021-08-21T17:20:12 Z JvThunder Distributing Candies (IOI21_candies) C++17
100 / 100
 469 ms 31376 KB 
#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;

const ll INF = (ll)(1e18);

struct segtree
{
    vector<ll> smx, smn, sum; 
    int N;
    segtree()
    {
        N = 1<<18;
        smx.assign(2*N,0);
        smn.assign(2*N,0);
        sum.assign(2*N,0);
    }

    void upd(ll v, int t, int node, int lx, int rx) 
    {
	    if(rx-lx==1) 
        {
            smx[node] = max(0LL, v);
            smn[node] = min(0LL, v);
            sum[node] = v;
            return;
        }
 
        int mid = (lx+rx)/2;
        if(t<mid) upd(v, t, 2*node, lx, mid);
        else upd(v, t, 2*node+1, mid, rx);
        
        sum[node] = sum[2*node]+sum[2*node+1];
        smx[node] = max(smx[2*node],sum[2*node]+smx[2*node+1]);
        smn[node] = min(smn[2*node],sum[2*node]+smn[2*node+1]);
    }
 
    ll get(ll c,int node, int lx, int rx) 
    {
        if(rx-lx==1) return min(max(sum[node], 0LL), c);
    
        int mid = (lx+rx)/2;
        if(smx[2*node+1]-smn[2*node+1]>c) return get(c, 2*node+1, mid, rx);
        ll a = get(c, 2*node, lx, mid);

        if(a+smx[2*node+1]>c) return c-(smx[2*node+1]-sum[2*node+1]);
        if(a+smn[2*node+1]<0) return sum[2*node+1]-smn[2*node+1];
        return a+sum[2*node+1];
    }

} st;
 
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) 
{
	int n=c.size(), q=l.size();
	vector<int> final_A; // final array
	vector<vector<int>> upd(n+1); // upd[i] store update at pos i

    // +1 to remove ambiguity of index 0 
    // positive or negative to show left or right
	for (int i=0; i<q; i++) upd[l[i]].pb(i+1), upd[r[i]+1].pb(-(i+1)); 
	for (int i=0; i<n; i++) 
    {
		for (auto j:upd[i]) 
        {
            // j is the update position
			if (j>0) --j, st.upd(v[j], j, 1, 0, q);
			else j=-j-1, st.upd(0, j, 1, 0, q);
		}
		final_A.pb(st.get(c[i], 1, 0, q));
	}
	return final_A;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12620 KB Output is correct
2 Correct 7 ms 12620 KB Output is correct
3 Correct 8 ms 12620 KB Output is correct
4 Correct 9 ms 12640 KB Output is correct
5 Correct 9 ms 12752 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 30996 KB Output is correct
2 Correct 446 ms 31376 KB Output is correct
3 Correct 438 ms 31036 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12620 KB Output is correct
2 Correct 272 ms 20436 KB Output is correct
3 Correct 82 ms 20996 KB Output is correct
4 Correct 465 ms 31024 KB Output is correct
5 Correct 449 ms 31036 KB Output is correct
6 Correct 442 ms 31036 KB Output is correct
7 Correct 443 ms 31224 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12620 KB Output is correct
2 Correct 7 ms 12628 KB Output is correct
3 Correct 127 ms 19692 KB Output is correct
4 Correct 75 ms 20696 KB Output is correct
5 Correct 197 ms 27300 KB Output is correct
6 Correct 202 ms 27240 KB Output is correct
7 Correct 210 ms 27288 KB Output is correct
8 Correct 199 ms 27284 KB Output is correct
9 Correct 204 ms 27312 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12620 KB Output is correct
2 Correct 7 ms 12620 KB Output is correct
3 Correct 8 ms 12620 KB Output is correct
4 Correct 9 ms 12640 KB Output is correct
5 Correct 9 ms 12752 KB Output is correct
6 Correct 466 ms 30996 KB Output is correct
7 Correct 446 ms 31376 KB Output is correct
8 Correct 438 ms 31036 KB Output is correct
9 Correct 7 ms 12620 KB Output is correct
10 Correct 272 ms 20436 KB Output is correct
11 Correct 82 ms 20996 KB Output is correct
12 Correct 465 ms 31024 KB Output is correct
13 Correct 449 ms 31036 KB Output is correct
14 Correct 442 ms 31036 KB Output is correct
15 Correct 443 ms 31224 KB Output is correct
16 Correct 7 ms 12620 KB Output is correct
17 Correct 7 ms 12628 KB Output is correct
18 Correct 127 ms 19692 KB Output is correct
19 Correct 75 ms 20696 KB Output is correct
20 Correct 197 ms 27300 KB Output is correct
21 Correct 202 ms 27240 KB Output is correct
22 Correct 210 ms 27288 KB Output is correct
23 Correct 199 ms 27284 KB Output is correct
24 Correct 204 ms 27312 KB Output is correct
25 Correct 7 ms 12620 KB Output is correct
26 Correct 94 ms 20924 KB Output is correct
27 Correct 264 ms 20340 KB Output is correct
28 Correct 443 ms 31124 KB Output is correct
29 Correct 469 ms 31032 KB Output is correct
30 Correct 438 ms 31000 KB Output is correct
31 Correct 450 ms 31020 KB Output is correct
32 Correct 455 ms 31100 KB Output is correct