oj.uz

Submission #816004

# Submission time Handle Problem Language Result Execution time Memory
816004 2023-08-09T03:39:43 Z alvingogo Distributing Candies (IOI21_candies) C++17
100 / 100
 336 ms 49776 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

typedef long long ll;
struct no{
    ll sum=0;
    ll mn=0,mx=0;
    ll ans=0;
};
struct ST{
    vector<no> st;
    void init(int x){
        st.resize(4*x);
    }
    void merge(no& v,no& a,no& b){
        v.sum=a.sum+b.sum;
        v.mn=min(b.mn,b.sum+a.mn);
        v.mx=max(b.mx,b.sum+a.mx);
        v.ans=max({a.ans,b.ans,(b.sum+a.mx)-b.mn,b.mx-(b.sum+a.mn)});
    }
    void update(int v,int L,int R,int p,int x){
        if(L==R){
            st[v].sum=x;
            st[v].mn=st[v].mx=x;
            return;
        }
        int m=(L+R)/2;
        if(p<=m){
            update(2*v+1,L,m,p,x);
        }
        else{
            update(2*v+2,m+1,R,p,x);
        }
        merge(st[v],st[2*v+1],st[2*v+2]);
    }
    no find(int v,int L,int R,int c,no& a){
        if(L==R){
            no h;
            merge(h,st[v],a);
            return h;
        }
        int m=(L+R)/2;
        no h;
        merge(h,st[2*v+2],a);
        if(h.ans>c){
            return find(2*v+2,m+1,R,c,a);
        }
        else{
            a=h;
            return find(2*v+1,L,m,c,a);
        }
    }
}st;
vector<int> distribute_candies(vector<int> w, vector<int> l,
                                    vector<int> r, vector<int> v) {
    int n=w.size();
    vector<int> ans(n);
    int q=l.size()+2;
    st.init(q);
    st.update(0,0,q-1,0,2e9);
    vector<vector<pair<int,int> > > upd(n),del(n);
    for(int i=0;i<q-2;i++){
        upd[l[i]].push_back({i+1,v[i]});
        del[r[i]].push_back({i+1,v[i]});
    }
    for(int i=0;i<n;i++){
        for(auto h:upd[i]){
            st.update(0,0,q-1,h.fs,-h.sc);
        }
        no e;
        auto d=st.find(0,0,q-1,w[i],e);
        if(d.mx-e.mn>w[i]){
            ans[i]=-e.mn;
        }
        else{
            ans[i]=w[i]-e.mx;
        }
        for(auto h:del[i]){
            st.update(0,0,q-1,h.fs,0);
        }
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 49740 KB Output is correct
2 Correct 333 ms 49740 KB Output is correct
3 Correct 324 ms 49736 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 203 ms 35716 KB Output is correct
3 Correct 52 ms 12420 KB Output is correct
4 Correct 325 ms 49736 KB Output is correct
5 Correct 304 ms 49636 KB Output is correct
6 Correct 316 ms 49612 KB Output is correct
7 Correct 307 ms 49672 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 115 ms 33476 KB Output is correct
4 Correct 51 ms 12356 KB Output is correct
5 Correct 172 ms 45160 KB Output is correct
6 Correct 174 ms 45140 KB Output is correct
7 Correct 171 ms 45140 KB Output is correct
8 Correct 172 ms 45156 KB Output is correct
9 Correct 184 ms 45164 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 313 ms 49740 KB Output is correct
7 Correct 333 ms 49740 KB Output is correct
8 Correct 324 ms 49736 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 203 ms 35716 KB Output is correct
11 Correct 52 ms 12420 KB Output is correct
12 Correct 325 ms 49736 KB Output is correct
13 Correct 304 ms 49636 KB Output is correct
14 Correct 316 ms 49612 KB Output is correct
15 Correct 307 ms 49672 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 115 ms 33476 KB Output is correct
19 Correct 51 ms 12356 KB Output is correct
20 Correct 172 ms 45160 KB Output is correct
21 Correct 174 ms 45140 KB Output is correct
22 Correct 171 ms 45140 KB Output is correct
23 Correct 172 ms 45156 KB Output is correct
24 Correct 184 ms 45164 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 51 ms 12356 KB Output is correct
27 Correct 178 ms 35736 KB Output is correct
28 Correct 336 ms 49736 KB Output is correct
29 Correct 316 ms 49652 KB Output is correct
30 Correct 317 ms 49776 KB Output is correct
31 Correct 315 ms 49740 KB Output is correct
32 Correct 329 ms 49748 KB Output is correct