oj.uz

Submission #467081

# Submission time Handle Problem Language Result Execution time Memory
467081 2021-08-21T16:49:13 Z JvThunder Distributing Candies (IOI21_candies) C++17
100 / 100
 494 ms 36968 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 6 ms 12620 KB Output is correct
2 Correct 6 ms 12536 KB Output is correct
3 Correct 8 ms 12656 KB Output is correct
4 Correct 8 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 458 ms 30424 KB Output is correct
2 Correct 445 ms 34360 KB Output is correct
3 Correct 432 ms 34152 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12640 KB Output is correct
2 Correct 273 ms 22756 KB Output is correct
3 Correct 88 ms 22332 KB Output is correct
4 Correct 443 ms 36200 KB Output is correct
5 Correct 459 ms 36668 KB Output is correct
6 Correct 494 ms 36968 KB Output is correct
7 Correct 443 ms 36340 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 12628 KB Output is correct
3 Correct 130 ms 21732 KB Output is correct
4 Correct 86 ms 21192 KB Output is correct
5 Correct 200 ms 30124 KB Output is correct
6 Correct 207 ms 30844 KB Output is correct
7 Correct 207 ms 31412 KB Output is correct
8 Correct 199 ms 30076 KB Output is correct
9 Correct 210 ms 31700 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12620 KB Output is correct
2 Correct 6 ms 12536 KB Output is correct
3 Correct 8 ms 12656 KB Output is correct
4 Correct 8 ms 12620 KB Output is correct
5 Correct 9 ms 12748 KB Output is correct
6 Correct 458 ms 30424 KB Output is correct
7 Correct 445 ms 34360 KB Output is correct
8 Correct 432 ms 34152 KB Output is correct
9 Correct 7 ms 12640 KB Output is correct
10 Correct 273 ms 22756 KB Output is correct
11 Correct 88 ms 22332 KB Output is correct
12 Correct 443 ms 36200 KB Output is correct
13 Correct 459 ms 36668 KB Output is correct
14 Correct 494 ms 36968 KB Output is correct
15 Correct 443 ms 36340 KB Output is correct
16 Correct 6 ms 12620 KB Output is correct
17 Correct 7 ms 12628 KB Output is correct
18 Correct 130 ms 21732 KB Output is correct
19 Correct 86 ms 21192 KB Output is correct
20 Correct 200 ms 30124 KB Output is correct
21 Correct 207 ms 30844 KB Output is correct
22 Correct 207 ms 31412 KB Output is correct
23 Correct 199 ms 30076 KB Output is correct
24 Correct 210 ms 31700 KB Output is correct
25 Correct 7 ms 12620 KB Output is correct
26 Correct 75 ms 21304 KB Output is correct
27 Correct 262 ms 22264 KB Output is correct
28 Correct 436 ms 34876 KB Output is correct
29 Correct 432 ms 35204 KB Output is correct
30 Correct 463 ms 35348 KB Output is correct
31 Correct 435 ms 35564 KB Output is correct
32 Correct 439 ms 35764 KB Output is correct