oj.uz

Submission #896984

# Submission time Handle Problem Language Result Execution time Memory
896984 2024-01-02T11:53:07 Z Faisal_Saqib Distributing Candies (IOI21_candies) C++17
8 / 100
 460 ms 49104 KB 
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>
#include <climits>
using namespace std;
#define ll long long
const ll inf=1e18;
const ll N=2e5+3;
int qp;
vector<pair<int,int>> T[N];
struct Data
{
    ll sum=0;
    ll mi=0;
    ll mx=0;
    ll lazy=0;
};
Data idendity{0,inf,-inf,0};
Data join(Data l,Data r)
{
    return Data{l.sum+r.sum,min(l.mi,r.mi),max(l.mx,r.mx),0};
}
struct SegmentTree
{
    Data val;
    int s,e;
    SegmentTree* next[2];
    SegmentTree(int l,int r)
    {
        s=l;
        e=r;
        if(s!=e)
        {
            int mid=(s+e)/2;
            next[0]=new SegmentTree(s,mid);
            next[1]=new SegmentTree(mid+1,e);
        }
    }
    void push()
    {
        val.sum+=(e-s+1)*val.lazy;
        val.mi+=val.lazy;
        val.mx+=val.lazy;
        if(s!=e)
        {
            next[0]->val.lazy+=val.lazy;
            next[1]->val.lazy+=val.lazy;
        }
        val.lazy=0;
    }
    void pull()
    {        
        val=join(next[0]->val,next[1]->val);
    }
    void Update(int l,int r,ll v)
    {
        push();
        if(r<s or e<l)
            return;
        if(l<=s and e<=r)
        {
            val.lazy+=v;
            push();
            return;
        }
        next[0]->Update(l,r,v);
        next[1]->Update(l,r,v);
        pull();
    }
    int Just(ll al,ll mx=-inf,ll mi=inf)
    {
        if(s==e)
        {
            return s;
        }
        else
        {
            ll nmx=max(mx,next[1]->val.mx);
            ll nmi=min(mi,next[1]->val.mi);
            if((nmx-nmi)>=al)
            {
                // answer is in the range
                return next[1]->Just(al);
            }
            else
            {
                return next[0]->Just(al,nmx,nmi);
            }
        }
    }
    Data get(int l,int r=qp)
    {
        push();
        if(r<s or e<l)
            return idendity;
        if(l<=s and e<=r)
            return val;
        return join(next[0]->get(l),next[1]->get(l));
    }
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v)
{
    int n=c.size();
    int q=l.size();
    qp=q;
    SegmentTree* st=new SegmentTree(0,qp);
    for(int i=0;i<q;i++)
    {
        T[l[i]].push_back({v[i],i+1});
        T[r[i]+1].push_back({-v[i],i+1});
    }
    vector<int> ans(n);
    ll tpot=0;
    for(int j=0;j<n;j++)
    {
        for(auto fi:T[j])
        {
            tpot+=fi.first;
            st->Update(fi.second,qp,fi.first);
        }
        long long cp=c[j];
        Data curap=st->get(0);
        if((curap.mx-curap.mi)<=cp)
        {
            ans[j]=(tpot-curap.mi);
            continue;
        }
        int s=st->Just(cp);
        curap=st->get(s);
        auto lpa=curap;
        curap=st->get(s+1) ;
        if(lpa.mx==curap.mx)
            ans[j]=tpot-lpa.mx+cp;
        else
            ans[j]=tpot-lpa.mi;
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Incorrect 2 ms 5468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 49104 KB Output is correct
2 Correct 453 ms 48212 KB Output is correct
3 Correct 460 ms 48172 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Incorrect 105 ms 40872 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Incorrect 2 ms 5468 KB Output isn't correct
4 Halted 0 ms 0 KB -