oj.uz

Submission #816001

# Submission time Handle Problem Language Result Execution time Memory
816001 2023-08-09T03:38:06 Z alvingogo Distributing Candies (IOI21_candies) C++17
100 / 100
 392 ms 62532 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;
pair<ll,int> operator+(pair<ll,int> a,pair<ll,int> b){
    return {a.fs+b.fs,b.sc};
}
struct no{
    ll sum=0;
    pair<ll,int> mn={0,0},mx={0,0};
    ll ans=0;
};
struct ST{
    vector<no> st;
    void init(int x){
        st.resize(4*x);
        build(0,0,x-1);
    }
    void build(int v,int L,int R){
        if(L==R){
            st[v].mn.sc=st[v].mx.sc=L;
            return;
        }
        int m=(L+R)/2;
        build(2*v+1,L,m);
        build(2*v+2,m+1,R);
        merge(st[v],st[2*v+1],st[2*v+2]);
    }
    void merge(no& v,no& a,no& b){
        v.sum=a.sum+b.sum;
        v.mn=min(b.mn,pair<ll,int>(b.sum,-1)+a.mn);
        v.mx=max(b.mx,pair<ll,int>(b.sum,-1)+a.mx);
        v.ans=max({a.ans,b.ans,(b.sum+a.mx.fs)-b.mn.fs,b.mx.fs-(b.sum+a.mn.fs)});
    }
    void update(int v,int L,int R,int p,int x){
        if(L==R){
            st[v].sum=x;
            st[v].mn.fs=st[v].mx.fs=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;
        e.mn.sc=e.mx.sc=q-1;
        auto d=st.find(0,0,q-1,w[i],e);
        if(d.mx.fs-e.mn.fs>w[i]){
            ans[i]=-e.mn.fs;
        }
        else{
            ans[i]=w[i]-e.mx.fs;
        }
        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 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 3 ms 980 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 62404 KB Output is correct
2 Correct 355 ms 62404 KB Output is correct
3 Correct 359 ms 62492 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 234 ms 48380 KB Output is correct
3 Correct 55 ms 12612 KB Output is correct
4 Correct 363 ms 62324 KB Output is correct
5 Correct 392 ms 62396 KB Output is correct
6 Correct 371 ms 62288 KB Output is correct
7 Correct 360 ms 62400 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 137 ms 46176 KB Output is correct
4 Correct 53 ms 12876 KB Output is correct
5 Correct 201 ms 58020 KB Output is correct
6 Correct 196 ms 58056 KB Output is correct
7 Correct 196 ms 58076 KB Output is correct
8 Correct 199 ms 58168 KB Output is correct
9 Correct 186 ms 58044 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 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 364 ms 62404 KB Output is correct
7 Correct 355 ms 62404 KB Output is correct
8 Correct 359 ms 62492 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 234 ms 48380 KB Output is correct
11 Correct 55 ms 12612 KB Output is correct
12 Correct 363 ms 62324 KB Output is correct
13 Correct 392 ms 62396 KB Output is correct
14 Correct 371 ms 62288 KB Output is correct
15 Correct 360 ms 62400 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 137 ms 46176 KB Output is correct
19 Correct 53 ms 12876 KB Output is correct
20 Correct 201 ms 58020 KB Output is correct
21 Correct 196 ms 58056 KB Output is correct
22 Correct 196 ms 58076 KB Output is correct
23 Correct 199 ms 58168 KB Output is correct
24 Correct 186 ms 58044 KB Output is correct
25 Correct 1 ms 300 KB Output is correct
26 Correct 56 ms 12952 KB Output is correct
27 Correct 238 ms 48512 KB Output is correct
28 Correct 374 ms 62396 KB Output is correct
29 Correct 380 ms 62532 KB Output is correct
30 Correct 376 ms 62404 KB Output is correct
31 Correct 391 ms 62412 KB Output is correct
32 Correct 372 ms 62416 KB Output is correct