oj.uz

답안 #467092

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467092 2021-08-21T17:17:28 Z JvThunder 사탕 분배 (IOI21_candies) C++17
100 / 100
 485 ms 30692 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(ll v, int t, int node, int lx, int rx) 
    {
	    if(rx-lx==1) 
        {
            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);
        
        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]);
    }
 
    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;
        if(smx[2*node+1]-smn[2*node+1]>c) return get(c, 2*node+1, mid, rx);
        ll a = get(c, 2*node, lx, mid);

        if(a+smx[2*node+1]>c) return c-(smx[2*node+1]-sum[2*node+1]);
        if(a+smn[2*node+1]<0) return sum[2*node+1]-smn[2*node+1];
        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>> q(N+1); // q[i] store update at pos i

    // +1 to remove ambiguity of index 0 
	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]) 
        {
            // j is the update position
			if (j>0) --j, st.upd(v[j], j, 1, 0, Q);
			else j=-j-1, st.upd(0, j, 1, 0, Q);
		}
		final_A.pb(st.get(c[i], 1, 0, Q));
	}
	return final_A;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12620 KB Output is correct
2 Correct 6 ms 12620 KB Output is correct
3 Correct 7 ms 12620 KB Output is correct
4 Correct 8 ms 12620 KB Output is correct
5 Correct 9 ms 12760 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 425 ms 30420 KB Output is correct
2 Correct 485 ms 30656 KB Output is correct
3 Correct 454 ms 30524 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12620 KB Output is correct
2 Correct 253 ms 19668 KB Output is correct
3 Correct 78 ms 20156 KB Output is correct
4 Correct 465 ms 30276 KB Output is correct
5 Correct 465 ms 30236 KB Output is correct
6 Correct 451 ms 30268 KB Output is correct
7 Correct 443 ms 30280 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12620 KB Output is correct
2 Correct 6 ms 12636 KB Output is correct
3 Correct 123 ms 19064 KB Output is correct
4 Correct 73 ms 20064 KB Output is correct
5 Correct 200 ms 26624 KB Output is correct
6 Correct 200 ms 26692 KB Output is correct
7 Correct 207 ms 26672 KB Output is correct
8 Correct 214 ms 26656 KB Output is correct
9 Correct 213 ms 26656 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12620 KB Output is correct
2 Correct 6 ms 12620 KB Output is correct
3 Correct 7 ms 12620 KB Output is correct
4 Correct 8 ms 12620 KB Output is correct
5 Correct 9 ms 12760 KB Output is correct
6 Correct 425 ms 30420 KB Output is correct
7 Correct 485 ms 30656 KB Output is correct
8 Correct 454 ms 30524 KB Output is correct
9 Correct 6 ms 12620 KB Output is correct
10 Correct 253 ms 19668 KB Output is correct
11 Correct 78 ms 20156 KB Output is correct
12 Correct 465 ms 30276 KB Output is correct
13 Correct 465 ms 30236 KB Output is correct
14 Correct 451 ms 30268 KB Output is correct
15 Correct 443 ms 30280 KB Output is correct
16 Correct 6 ms 12620 KB Output is correct
17 Correct 6 ms 12636 KB Output is correct
18 Correct 123 ms 19064 KB Output is correct
19 Correct 73 ms 20064 KB Output is correct
20 Correct 200 ms 26624 KB Output is correct
21 Correct 200 ms 26692 KB Output is correct
22 Correct 207 ms 26672 KB Output is correct
23 Correct 214 ms 26656 KB Output is correct
24 Correct 213 ms 26656 KB Output is correct
25 Correct 6 ms 12620 KB Output is correct
26 Correct 78 ms 20412 KB Output is correct
27 Correct 262 ms 19916 KB Output is correct
28 Correct 456 ms 30488 KB Output is correct
29 Correct 428 ms 30504 KB Output is correct
30 Correct 440 ms 30692 KB Output is correct
31 Correct 445 ms 30628 KB Output is correct
32 Correct 435 ms 30528 KB Output is correct