oj.uz

Submission #467225

# Submission time Handle Problem Language Result Execution time Memory
467225 2021-08-22T06:11:43 Z JvThunder Distributing Candies (IOI21_candies) C++17
100 / 100
 489 ms 35188 KB 
#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;

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

// make a segtree where each leaf represents
struct segtree
{
    vector<ll> smx, smn, sum; 
    int N;
    segtree()
    {
        N = 1<<18;
        smx.assign(2*N,0); // suffix max
        smn.assign(2*N,0); // suffix min
        sum.assign(2*N,0); // range sum
    }

    void upd(ll v, int t, int node, int lx, int rx) // updates val v into position t 
    {
	    if(rx-lx==1) 
        {
            // set leaf to v
            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);
        
        // change values after update
        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]);
        return;
    }
    
    // return the sum of the suffix of the last index smx-smn>c 
    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;

        // binary search last index smx-smn>c    
        // if found in right side, directly go right
        if(smx[2*node+1]-smn[2*node+1]>c) return get(c, 2*node+1, mid, rx);
        
        // else go left
        ll a = get(c, 2*node, lx, mid);
        // guarantees no touching the bottom
        if(a+smx[2*node+1]>c) return c-(smx[2*node+1]-sum[2*node+1]);
        // guarantees no touching the top
        if(a+smn[2*node+1]<0) return 0+(sum[2*node+1]-smn[2*node+1]);
        // guarantees no touching both
        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

    // positive or negative to show left or right
	for (int i=1; i<=q; i++) upd[l[i-1]].pb(i), upd[r[i-1]+1].pb(-i); 
	for (int i=0; i<n; i++) 
    {
		for (auto j:upd[i]) 
        {
            // j is the index of query
			if (j>0) st.upd(v[j-1], j-1, 1, 0, q);
			else st.upd(0, -j-1, 1, 0, q); // set back pos x to 0
		}
		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 9 ms 12620 KB Output is correct
2 Correct 7 ms 12596 KB Output is correct
3 Correct 8 ms 12620 KB Output is correct
4 Correct 9 ms 12636 KB Output is correct
5 Correct 9 ms 12744 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 30328 KB Output is correct
2 Correct 453 ms 30336 KB Output is correct
3 Correct 457 ms 30272 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 277 ms 19588 KB Output is correct
3 Correct 81 ms 22328 KB Output is correct
4 Correct 467 ms 35100 KB Output is correct
5 Correct 446 ms 35044 KB Output is correct
6 Correct 433 ms 35024 KB Output is correct
7 Correct 430 ms 34980 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12620 KB Output is correct
2 Correct 6 ms 12620 KB Output is correct
3 Correct 127 ms 19128 KB Output is correct
4 Correct 75 ms 21312 KB Output is correct
5 Correct 200 ms 30160 KB Output is correct
6 Correct 207 ms 30772 KB Output is correct
7 Correct 215 ms 31408 KB Output is correct
8 Correct 200 ms 30044 KB Output is correct
9 Correct 210 ms 31468 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12620 KB Output is correct
2 Correct 7 ms 12596 KB Output is correct
3 Correct 8 ms 12620 KB Output is correct
4 Correct 9 ms 12636 KB Output is correct
5 Correct 9 ms 12744 KB Output is correct
6 Correct 459 ms 30328 KB Output is correct
7 Correct 453 ms 30336 KB Output is correct
8 Correct 457 ms 30272 KB Output is correct
9 Correct 7 ms 12620 KB Output is correct
10 Correct 277 ms 19588 KB Output is correct
11 Correct 81 ms 22328 KB Output is correct
12 Correct 467 ms 35100 KB Output is correct
13 Correct 446 ms 35044 KB Output is correct
14 Correct 433 ms 35024 KB Output is correct
15 Correct 430 ms 34980 KB Output is correct
16 Correct 6 ms 12620 KB Output is correct
17 Correct 6 ms 12620 KB Output is correct
18 Correct 127 ms 19128 KB Output is correct
19 Correct 75 ms 21312 KB Output is correct
20 Correct 200 ms 30160 KB Output is correct
21 Correct 207 ms 30772 KB Output is correct
22 Correct 215 ms 31408 KB Output is correct
23 Correct 200 ms 30044 KB Output is correct
24 Correct 210 ms 31468 KB Output is correct
25 Correct 6 ms 12624 KB Output is correct
26 Correct 78 ms 21308 KB Output is correct
27 Correct 276 ms 22268 KB Output is correct
28 Correct 489 ms 34896 KB Output is correct
29 Correct 463 ms 35188 KB Output is correct
30 Correct 446 ms 35060 KB Output is correct
31 Correct 456 ms 34996 KB Output is correct
32 Correct 449 ms 34984 KB Output is correct