oj.uz

Submission #1055274

# Submission time Handle Problem Language Result Execution time Memory
1055274 2024-08-12T16:16:34 Z Huseyn123 Distributing Candies (IOI21_candies) C++17
100 / 100
 2126 ms 47208 KB 
#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
#define INF LLONG_MAX
#define pb push_back
using namespace std;
typedef long long ll;
vector<vector<int>> s,e;
struct segtree_min{
    vector<ll> mins;
    vector<ll> lazy;
    int size;
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        mins.assign(2*size,0LL);
        lazy.assign(2*size,0LL);
    }
    void build(int x,int lx,int rx,vector<int> &a){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                mins[x]=a[lx];
            }
            return;
        }
        int m=(lx+rx)/2;
        build(2*x+1,lx,m,a);
        build(2*x+2,m,rx,a);
        mins[x]=min(mins[2*x+1],mins[2*x+2]);
    }
    void build(vector<int> &a){
        build(0,0,size,a);
    }
    void propogate(int x,int lx,int rx){
        if(rx-lx==1){
            return;
        }
        mins[2*x+1]+=lazy[x];
        mins[2*x+2]+=lazy[x];
        lazy[2*x+1]+=lazy[x];
        lazy[2*x+2]+=lazy[x];
        lazy[x]=0;
    }
    void upd(int x,int lx,int rx,int l,int r,int v){
        propogate(x,lx,rx);
        if(rx<=l || lx>=r){
            return;
        }
        if(lx>=l && rx<=r){
            mins[x]+=v;
            lazy[x]+=v;
            return;
        }
        int m=(lx+rx)/2;
        upd(2*x+1,lx,m,l,r,v);
        upd(2*x+2,m,rx,l,r,v);
        mins[x]=min(mins[2*x+1],mins[2*x+2]);
    }
    void upd(int l,int r,int v){
        return upd(0,0,size,l,r,v);
    }
    ll get(int x,int lx,int rx,int l,int r){
        propogate(x,lx,rx);
        if(rx<=l || lx>=r){
            return INF;
        }
        if(lx>=l && rx<=r){
            return mins[x];
        }
        int m=(lx+rx)/2;
        ll s1,s2;
        s1=get(2*x+1,lx,m,l,r);
        s2=get(2*x+2,m,rx,l,r);
        return min(s1,s2);
    }
    ll get(int l,int r){
        return get(0,0,size,l,r);
    }
};
struct segtree_max{
    vector<ll> maxs;
    vector<ll> lazy;
    int size;
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        maxs.assign(2*size,0LL);
        lazy.assign(2*size,0LL);
    }
    void build(int x,int lx,int rx,vector<int> &a){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                maxs[x]=a[lx];
            }
            return;
        }
        int m=(lx+rx)/2;
        build(2*x+1,lx,m,a);
        build(2*x+2,m,rx,a);
        maxs[x]=max(maxs[2*x+1],maxs[2*x+2]);
    }
    void build(vector<int> &a){
        build(0,0,size,a);
    }
    void propogate(int x,int lx,int rx){
        if(rx-lx==1){
            return;
        }
        maxs[2*x+1]+=lazy[x];
        maxs[2*x+2]+=lazy[x];
        lazy[2*x+1]+=lazy[x];
        lazy[2*x+2]+=lazy[x];
        lazy[x]=0;
    }
    void upd(int x,int lx,int rx,int l,int r,int v){
        propogate(x,lx,rx);
        if(rx<=l || lx>=r){
            return;
        }
        if(lx>=l && rx<=r){
            maxs[x]+=v;
            lazy[x]+=v;
            return;
        }
        int m=(lx+rx)/2;
        upd(2*x+1,lx,m,l,r,v);
        upd(2*x+2,m,rx,l,r,v);
        maxs[x]=max(maxs[2*x+1],maxs[2*x+2]);
    }
    void upd(int l,int r,int v){
        return upd(0,0,size,l,r,v);
    }
    ll get(int x,int lx,int rx,int l,int r){
        propogate(x,lx,rx);
        if(rx<=l || lx>=r){
            return -INF;
        }
        if(lx>=l && rx<=r){
            return maxs[x];
        }
        int m=(lx+rx)/2;
        ll s1,s2;
        s1=get(2*x+1,lx,m,l,r);
        s2=get(2*x+2,m,rx,l,r);
        return max(s1,s2);
    }
    ll get(int l,int r){
        return get(0,0,size,l,r);
    }
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    int q = l.size();
    vector<int> ans(n);
    s.resize(n);
    e.resize(n);
    for(int i=0;i<q;i++){
        s[l[i]].pb(i); 
        e[r[i]].pb(i);
    }
    segtree_min stmin;
    segtree_max stmax;
    stmin.init(q); 
    stmax.init(q);
    for(int i=0;i<n;i++){
        for(auto x:s[i]){
            stmin.upd(x,q,v[x]);
            stmax.upd(x,q,v[x]);
        }
        int l,r,mid; 
        l=0; 
        r=q-1; 
        while(l<r){
            mid=(l+r+1)/2;
            if(stmax.get(mid,q)-stmin.get(mid,q)>=c[i]){
                l=mid;
            }
            else{
                r=mid-1;
            }
        }
        ll res=0;
        if(stmax.get(l,q)-stmin.get(l,q)>=c[i]){
            if(stmax.get(l,l+1)==stmax.get(l,q)){
                res=-stmin.get(l,q);
                if(l+1<q){
                    ll mx=stmax.get(l+1,q);
                    if(res+mx>c[i]){
                        res=c[i]-mx;
                    }
                }
            }
            else{
                res=c[i]-stmax.get(l,q);
                if(l+1<q){
                    ll mn=stmin.get(l+1,q);
                    if(res+mn<0){
                        res=-mn;
                    }
                }
            }
        }
        else{
            ll mx=stmax.get(0,q);
            ll mn=stmin.get(0,q);
            if(mx>c[i]){
                res=c[i]-mx;
            }
            if(mn<0){
                res=-mn;
            }
        }
        ans[i]=res+stmax.get(q-1,q);
        for(auto x:e[i]){
            stmin.upd(x,q,-v[x]);
            stmax.upd(x,q,-v[x]);
        }
    }
    /*
        ll val[q+1];
        pair<ll,ll> mn[q+1],mx[q+1];
        val[0]=0;
        for(int i=1;i<=q;i++){
            val[i]=v[i-1];
            val[i]+=val[i-1];
        }
        mn[q]={val[q],q}; 
        mx[q]={val[q],q};
        for(int i=q-1;i>=1;i--){
            mn[i]={val[i],(ll)i};
            mx[i]={val[i],(ll)i};
            if(mn[i+1].first<=val[i]){
                mn[i]=mn[i+1];
            }
            if(mx[i+1].first>=val[i]){
                mx[i]=mx[i+1];
            }
        }
        int ind=1;
        while(ind<=q){
            e.push_back({mx[ind].first-mn[ind].first,mx[ind].second,mn[ind].second});
            ind=max(mx[ind].second,mn[ind].second)+1;
        }
        int sz=(int)e.size();
        for(int i=0;i<n;i++){
            int l,r,mid;
            l=0; 
            r=sz-1;
            while(l<r){
                mid=(l+r)/2; 
                if(e[mid][0]<c[i]){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            ll res=0;
            if(e[l][0]<c[i]){
                if(l){
                    if(e[l-1][1]>e[l-1][2]){
                        res+=c[i]-val[e[l-1][1]];
                    }
                    else{
                        res-=val[e[l-1][2]];
                    }
                }
                if(val[e[l][1]]+res>c[i]){
                    res=c[i]-val[e[l][1]];
                }
                if(val[e[l][2]]+res<0){
                    res=-val[e[l][2]];
                }
            }
            else{
                if(e[sz-1][1]>e[sz-1][2]){
                    res+=c[i]-val[e[sz-1][1]];
                }
                else{
                    res-=val[e[sz-1][2]];
                }
            }
            s[i]=val[q]+res;
        }
    */
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 7 ms 836 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1710 ms 45140 KB Output is correct
2 Correct 1866 ms 44368 KB Output is correct
3 Correct 1832 ms 44404 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 390 ms 27520 KB Output is correct
3 Correct 566 ms 15676 KB Output is correct
4 Correct 2126 ms 46424 KB Output is correct
5 Correct 1936 ms 46816 KB Output is correct
6 Correct 1681 ms 47208 KB Output is correct
7 Correct 1703 ms 46544 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 282 ms 26008 KB Output is correct
4 Correct 421 ms 13528 KB Output is correct
5 Correct 1788 ms 38616 KB Output is correct
6 Correct 1573 ms 39288 KB Output is correct
7 Correct 1409 ms 39868 KB Output is correct
8 Correct 1728 ms 38508 KB Output is correct
9 Correct 2016 ms 39988 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 7 ms 836 KB Output is correct
6 Correct 1710 ms 45140 KB Output is correct
7 Correct 1866 ms 44368 KB Output is correct
8 Correct 1832 ms 44404 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 390 ms 27520 KB Output is correct
11 Correct 566 ms 15676 KB Output is correct
12 Correct 2126 ms 46424 KB Output is correct
13 Correct 1936 ms 46816 KB Output is correct
14 Correct 1681 ms 47208 KB Output is correct
15 Correct 1703 ms 46544 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 282 ms 26008 KB Output is correct
19 Correct 421 ms 13528 KB Output is correct
20 Correct 1788 ms 38616 KB Output is correct
21 Correct 1573 ms 39288 KB Output is correct
22 Correct 1409 ms 39868 KB Output is correct
23 Correct 1728 ms 38508 KB Output is correct
24 Correct 2016 ms 39988 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 507 ms 13688 KB Output is correct
27 Correct 337 ms 27132 KB Output is correct
28 Correct 1853 ms 45052 KB Output is correct
29 Correct 1827 ms 45284 KB Output is correct
30 Correct 1786 ms 45636 KB Output is correct
31 Correct 1733 ms 45680 KB Output is correct
32 Correct 1615 ms 45908 KB Output is correct