oj.uz

Submission #830125

# Submission time Handle Problem Language Result Execution time Memory
830125 2023-08-18T19:14:38 Z tigran Distributing Candies (IOI21_candies) C++17
100 / 100
 339 ms 55272 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 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 314 ms 49740 KB Output is correct
2 Correct 319 ms 49748 KB Output is correct
3 Correct 314 ms 49612 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 183 ms 35712 KB Output is correct
3 Correct 61 ms 12464 KB Output is correct
4 Correct 330 ms 49632 KB Output is correct
5 Correct 321 ms 49736 KB Output is correct
6 Correct 339 ms 49764 KB Output is correct
7 Correct 301 ms 49736 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 1 ms 340 KB Output is correct
3 Correct 122 ms 33496 KB Output is correct
4 Correct 50 ms 12344 KB Output is correct
5 Correct 173 ms 45140 KB Output is correct
6 Correct 174 ms 45156 KB Output is correct
7 Correct 188 ms 45252 KB Output is correct
8 Correct 173 ms 45172 KB Output is correct
9 Correct 171 ms 45132 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 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 314 ms 49740 KB Output is correct
7 Correct 319 ms 49748 KB Output is correct
8 Correct 314 ms 49612 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 183 ms 35712 KB Output is correct
11 Correct 61 ms 12464 KB Output is correct
12 Correct 330 ms 49632 KB Output is correct
13 Correct 321 ms 49736 KB Output is correct
14 Correct 339 ms 49764 KB Output is correct
15 Correct 301 ms 49736 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 122 ms 33496 KB Output is correct
19 Correct 50 ms 12344 KB Output is correct
20 Correct 173 ms 45140 KB Output is correct
21 Correct 174 ms 45156 KB Output is correct
22 Correct 188 ms 45252 KB Output is correct
23 Correct 173 ms 45172 KB Output is correct
24 Correct 171 ms 45132 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 52 ms 12356 KB Output is correct
27 Correct 178 ms 38344 KB Output is correct
28 Correct 306 ms 54284 KB Output is correct
29 Correct 312 ms 54568 KB Output is correct
30 Correct 316 ms 54752 KB Output is correct
31 Correct 308 ms 54956 KB Output is correct
32 Correct 323 ms 55272 KB Output is correct