oj.uz

Submission #467047

# Submission time Handle Problem Language Result Execution time Memory
467047 2021-08-21T12:30:19 Z JvThunder Distributing Candies (IOI21_candies) C++17
100 / 100
 489 ms 37084 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) j--, st.upd(1, 0, Q-1, j, v[j]);
			else j=-j-1, st.upd(1, 0, Q-1, j, 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 7 ms 12620 KB Output is correct
2 Correct 6 ms 12552 KB Output is correct
3 Correct 8 ms 12620 KB Output is correct
4 Correct 10 ms 12620 KB Output is correct
5 Correct 9 ms 12748 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 30720 KB Output is correct
2 Correct 460 ms 34304 KB Output is correct
3 Correct 450 ms 34108 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 275 ms 22668 KB Output is correct
3 Correct 80 ms 22348 KB Output is correct
4 Correct 441 ms 36316 KB Output is correct
5 Correct 431 ms 36548 KB Output is correct
6 Correct 437 ms 37084 KB Output is correct
7 Correct 417 ms 36284 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 12624 KB Output is correct
3 Correct 129 ms 19516 KB Output is correct
4 Correct 73 ms 20436 KB Output is correct
5 Correct 199 ms 27056 KB Output is correct
6 Correct 206 ms 27040 KB Output is correct
7 Correct 203 ms 27076 KB Output is correct
8 Correct 204 ms 27084 KB Output is correct
9 Correct 215 ms 27056 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 6 ms 12552 KB Output is correct
3 Correct 8 ms 12620 KB Output is correct
4 Correct 10 ms 12620 KB Output is correct
5 Correct 9 ms 12748 KB Output is correct
6 Correct 435 ms 30720 KB Output is correct
7 Correct 460 ms 34304 KB Output is correct
8 Correct 450 ms 34108 KB Output is correct
9 Correct 7 ms 12620 KB Output is correct
10 Correct 275 ms 22668 KB Output is correct
11 Correct 80 ms 22348 KB Output is correct
12 Correct 441 ms 36316 KB Output is correct
13 Correct 431 ms 36548 KB Output is correct
14 Correct 437 ms 37084 KB Output is correct
15 Correct 417 ms 36284 KB Output is correct
16 Correct 6 ms 12620 KB Output is correct
17 Correct 7 ms 12624 KB Output is correct
18 Correct 129 ms 19516 KB Output is correct
19 Correct 73 ms 20436 KB Output is correct
20 Correct 199 ms 27056 KB Output is correct
21 Correct 206 ms 27040 KB Output is correct
22 Correct 203 ms 27076 KB Output is correct
23 Correct 204 ms 27084 KB Output is correct
24 Correct 215 ms 27056 KB Output is correct
25 Correct 7 ms 12588 KB Output is correct
26 Correct 75 ms 21328 KB Output is correct
27 Correct 263 ms 22384 KB Output is correct
28 Correct 427 ms 34748 KB Output is correct
29 Correct 453 ms 35276 KB Output is correct
30 Correct 489 ms 35356 KB Output is correct
31 Correct 426 ms 35640 KB Output is correct
32 Correct 460 ms 35840 KB Output is correct