oj.uz

Submission #467084

# Submission time Handle Problem Language Result Execution time Memory
467084 2021-08-21T16:51:20 Z JvThunder Distributing Candies (IOI21_candies) C++17
100 / 100
 495 ms 30784 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(int i, int s, int e, int t, ll v) 
    {
	    if(s==e) 
        {
            smx[i] = max(0LL, v);
            smn[i] = min(0LL, v);
            sum[i] = v;
            return;
        }
 
        int m=(s+e)/2;
        if(t<=m) upd(2*i, s, m, t, v);
        else upd(2*i+1, m+1, e, t, v);
        
        sum[i] = sum[2*i]+sum[2*i+1];
        smx[i] = max(smx[2*i],sum[2*i]+smx[2*i+1]);
        smn[i] = min(smn[2*i],sum[2*i]+smn[2*i+1]);
    }
 
    ll get(int i, int s, int e, ll c) 
    {
        if(s==e) return min(max(sum[i], 0LL), c);
    
        int m = (s+e)/2;
        if(smx[2*i+1]-smn[2*i+1]>c) return get(2*i+1, m+1, e, c);
    
        ll r = get(2*i,s,m,c);
        if(r+smx[2*i+1]>c) return c-(smx[2*i+1]-sum[2*i+1]);
        if(r+smn[2*i+1]<0) return sum[2*i+1]-smn[2*i+1];
        return r+sum[2*i+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;
	vector<vector<int>> q(N+1);

	for (int i=0; i<Q; i++) q[l[i]].pb(i+1), q[r[i]+1].pb(-(i+1));
	for (int i=0; i<N; i++) 
    {
		for (auto j:q[i]) 
        {
			if (j>=0) st.upd(1, 0, Q-1, j-1, v[j-1]);
			else st.upd(1, 0, Q-1, -j-1, 0);
		}
		final_A.pb(st.get(1, 0, Q-1, c[i]));
	}
	return final_A;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12620 KB Output is correct
2 Correct 6 ms 12524 KB Output is correct
3 Correct 7 ms 12620 KB Output is correct
4 Correct 7 ms 12644 KB Output is correct
5 Correct 8 ms 12748 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 30276 KB Output is correct
2 Correct 468 ms 30784 KB Output is correct
3 Correct 416 ms 30596 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12620 KB Output is correct
2 Correct 275 ms 20080 KB Output is correct
3 Correct 82 ms 20576 KB Output is correct
4 Correct 461 ms 30676 KB Output is correct
5 Correct 446 ms 30656 KB Output is correct
6 Correct 431 ms 30636 KB Output is correct
7 Correct 431 ms 30692 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 7 ms 12564 KB Output is correct
3 Correct 127 ms 19364 KB Output is correct
4 Correct 74 ms 20316 KB Output is correct
5 Correct 199 ms 26864 KB Output is correct
6 Correct 205 ms 26964 KB Output is correct
7 Correct 204 ms 26928 KB Output is correct
8 Correct 199 ms 26912 KB Output is correct
9 Correct 205 ms 26912 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12620 KB Output is correct
2 Correct 6 ms 12524 KB Output is correct
3 Correct 7 ms 12620 KB Output is correct
4 Correct 7 ms 12644 KB Output is correct
5 Correct 8 ms 12748 KB Output is correct
6 Correct 434 ms 30276 KB Output is correct
7 Correct 468 ms 30784 KB Output is correct
8 Correct 416 ms 30596 KB Output is correct
9 Correct 6 ms 12620 KB Output is correct
10 Correct 275 ms 20080 KB Output is correct
11 Correct 82 ms 20576 KB Output is correct
12 Correct 461 ms 30676 KB Output is correct
13 Correct 446 ms 30656 KB Output is correct
14 Correct 431 ms 30636 KB Output is correct
15 Correct 431 ms 30692 KB Output is correct
16 Correct 6 ms 12620 KB Output is correct
17 Correct 7 ms 12564 KB Output is correct
18 Correct 127 ms 19364 KB Output is correct
19 Correct 74 ms 20316 KB Output is correct
20 Correct 199 ms 26864 KB Output is correct
21 Correct 205 ms 26964 KB Output is correct
22 Correct 204 ms 26928 KB Output is correct
23 Correct 199 ms 26912 KB Output is correct
24 Correct 205 ms 26912 KB Output is correct
25 Correct 6 ms 12620 KB Output is correct
26 Correct 79 ms 20496 KB Output is correct
27 Correct 275 ms 20232 KB Output is correct
28 Correct 422 ms 30672 KB Output is correct
29 Correct 495 ms 30692 KB Output is correct
30 Correct 425 ms 30652 KB Output is correct
31 Correct 474 ms 30636 KB Output is correct
32 Correct 446 ms 30684 KB Output is correct