oj.uz

Submission #467224

# Submission time Handle Problem Language Result Execution time Memory
467224 2021-08-22T06:10:53 Z JvThunder Distributing Candies (IOI21_candies) C++17
8 / 100
 478 ms 35052 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[node]-sum[node]);
        // guarantees no touching the top
        if(a+smn[2*node+1]<0) return 0+(sum[node]-smn[node]);
        // 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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12620 KB Output is correct
2 Correct 7 ms 12620 KB Output is correct
3 Correct 8 ms 12748 KB Output is correct
4 Correct 8 ms 12640 KB Output is correct
5 Incorrect 9 ms 12760 KB Output isn't correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 35052 KB Output is correct
2 Correct 460 ms 34304 KB Output is correct
3 Correct 478 ms 34428 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12620 KB Output is correct
2 Incorrect 276 ms 22672 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12620 KB Output is correct
2 Correct 8 ms 12652 KB Output is correct
3 Incorrect 128 ms 21748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12620 KB Output is correct
2 Correct 7 ms 12620 KB Output is correct
3 Correct 8 ms 12748 KB Output is correct
4 Correct 8 ms 12640 KB Output is correct
5 Incorrect 9 ms 12760 KB Output isn't correct