oj.uz

Submission #795905

# Submission time Handle Problem Language Result Execution time Memory
795905 2023-07-27T21:35:25 Z amin Distributing Candies (IOI21_candies) C++17
100 / 100
 916 ms 46836 KB 
#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ll long long

ll masuf[1000000],misuf[1000000],sum[1000000];
ll a[1000000];
ll o=0;
ll minin[1000000],maxin[1000000];
void update(int v,int tl,int tr,int pos)
{
    if(pos>tr||pos<tl)
        return ;
    if(tl==tr)
    {
        masuf[v]=a[pos];
        misuf[v]=a[pos];
        sum[v]=a[pos];
        maxin[v]=tl;
        minin[v]=tl;
        return ;
    }
    int tm=(tl+tr)/2;
    update(v*2,tl,tm,pos);
    update(v*2+1,tm+1,tr,pos);
    sum[v]=sum[v*2]+sum[v*2+1];
    if(misuf[v*2+1]<=sum[v*2+1]+misuf[v*2])
    {
        minin[v]=minin[v*2+1];
    }else
    minin[v]=minin[v*2];
     if(masuf[v*2+1]>=sum[v*2+1]+masuf[v*2])
    {
        maxin[v]=maxin[v*2+1];
    }else
    maxin[v]=maxin[v*2];
    misuf[v]=min(misuf[v*2+1],sum[v*2+1]+misuf[v*2]);
    masuf[v]=max(masuf[v*2+1],sum[v*2+1]+masuf[v*2]);
}
ll get(int v,int tl,int tr,int l,int r)
{
    if(l>r)
        return 0;
    if(tl==l&&tr==r)
    {
        return sum[v];
    }
    int tm=(tl+tr)/2;
    if(r<=tm)
    {
        return get(v*2,tl,tm,l,r);
    }
    if(l>tm)
    {
        return get(v*2+1,tm+1,tr,l,r);
    }
   return get(v*2,tl,tm,l,tm)+get(v*2+1,tm+1,tr,tm+1,r);
}
pair<ll,pair<ll,ll> > getmin(int v,int tl,int tr,int l,int r)
{
     if(tl==l&&tr==r)
    {
        return {sum[v],{misuf[v],minin[v]}};
    }
    int tm=(tl+tr)/2;
    if(r<=tm)
    {
        return getmin(v*2,tl,tm,l,r);
    }
    if(l>tm)
    {
        return getmin(v*2+1,tm+1,tr,l,r);
    }
pair<ll,pair<ll,ll> >f=getmin(v*2,tl,tm,l,tm);
pair<ll,pair<ll,ll> >s=getmin(v*2+1,tm+1,tr,tm+1,r);
if(s.second.first<=s.first+f.second.first)
{
    return{f.first+s.first,{min(s.second.first,s.first+f.second.first),s.second.second}};
}else
   return {f.first+s.first,{min(s.second.first,s.first+f.second.first),f.second.second}};
}
pair<ll,pair<ll,ll > > getmax(int v,int tl,int tr,int l,int r)
{
     if(tl==l&&tr==r)
    {
        return {sum[v],{masuf[v],maxin[v]}};
    }
    int tm=(tl+tr)/2;
    if(r<=tm)
    {
        return getmax(v*2,tl,tm,l,r);
    }
    if(l>tm)
    {
        return getmax(v*2+1,tm+1,tr,l,r);
    }
pair<ll,pair<ll,ll> >f=getmax(v*2,tl,tm,l,tm);
pair<ll,pair<ll,ll> >s=getmax(v*2+1,tm+1,tr,tm+1,r);

if(s.second.first>=s.first+f.second.first)
{
    return{f.first+s.first,{max(s.second.first,s.first+f.second.first),s.second.second}};
}else
   return {f.first+s.first,{max(s.second.first,s.first+f.second.first),f.second.second}};


}
vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v)
{
     int n=c.size();
     vector<int>ans;
     vector<int>act[n+1];
     int q=l.size();
     for(int i=0;i<q;i++)
     {

         act[l[i]].push_back(i);
         act[r[i]+1].push_back(i);
         update(1,0,q-1,i);
     }

     for(int i=0;i<n;i++)
     {

         for(auto y:act[i])
         {
             if(a[y]!=v[y])
             {
                 a[y]=v[y];
                 update(1,0,q-1,y);
             }else
             {
                 a[y]=0;
                 update(1,0,q-1,y);
             }
         }

         int l=-1;
         int r=q;
         while(l+1<r)
         {
             int m=(l+r)/2;
             ll mi=min(o,getmin(1,0,q-1,m,q-1).second.first);
             ll ma=max(o,getmax(1,0,q-1,m,q-1).second.first);
          //   cout<<m<<' '<<mi<<' '<<ma<<endl;
             if(abs(ma-mi)>=c[i])
             {
                 l=m;
             }else
             r=m;
         }
        // cout<<r<<endl;
         ll en=0;
    if(l==-1||a[l]<0)
    {
        if(r==q||(getmax(1,0,q-1,r,q-1).second.first==0&&getmin(1,0,q-1,r,q-1).second.first==0))
        {
            ans.push_back(0);
            continue;
        }
         en=getmax(1,0,q-1,r,q-1).second.second;
if(getmax(1,0,q-1,r,q-1).second.first<o)
{
    ans.push_back(0);
    continue;
}
   // en--;
ans.push_back(get(1,0,q-1,en,q-1));
    }
    if(a[l]>0)
    {
        if(r==q||(getmin(1,0,q-1,r,q-1).second.first==0&&getmin(1,0,q-1,r,q-1).second.first==0))
        {
            ans.push_back(c[i]);
            continue;
        }
        en=getmin(1,0,q-1,r,q-1).second.second;
      //  cout<<en<<' '<<getmin(1,0,q-1,r,q-1).second.first<<' '<<get(1,0,q-1,r,q-1)<<' ';
if(getmin(1,0,q-1,r,q-1).second.first>o)
{
    ans.push_back(c[i]);
    continue;
}
 //   cout<<en<<' ';

      //  cout<<get(1,0,q-1,en,q-1)<<endl;
        ans.push_back(c[i]+get(1,0,q-1,en,q-1));
     }


     }
     return ans;
}

Subtask #1
3.0 / 3.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 40116 KB Output is correct
2 Correct 876 ms 40216 KB Output is correct
3 Correct 882 ms 40168 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 310 ms 29472 KB Output is correct
3 Correct 233 ms 8996 KB Output is correct
4 Correct 916 ms 46036 KB Output is correct
5 Correct 791 ms 46424 KB Output is correct
6 Correct 661 ms 46836 KB Output is correct
7 Correct 647 ms 46300 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 121 ms 28808 KB Output is correct
4 Correct 149 ms 7980 KB Output is correct
5 Correct 515 ms 36480 KB Output is correct
6 Correct 471 ms 36604 KB Output is correct
7 Correct 378 ms 36500 KB Output is correct
8 Correct 545 ms 36508 KB Output is correct
9 Correct 678 ms 36436 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 761 ms 40116 KB Output is correct
7 Correct 876 ms 40216 KB Output is correct
8 Correct 882 ms 40168 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 310 ms 29472 KB Output is correct
11 Correct 233 ms 8996 KB Output is correct
12 Correct 916 ms 46036 KB Output is correct
13 Correct 791 ms 46424 KB Output is correct
14 Correct 661 ms 46836 KB Output is correct
15 Correct 647 ms 46300 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 121 ms 28808 KB Output is correct
19 Correct 149 ms 7980 KB Output is correct
20 Correct 515 ms 36480 KB Output is correct
21 Correct 471 ms 36604 KB Output is correct
22 Correct 378 ms 36500 KB Output is correct
23 Correct 545 ms 36508 KB Output is correct
24 Correct 678 ms 36436 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 194 ms 9244 KB Output is correct
27 Correct 305 ms 32100 KB Output is correct
28 Correct 797 ms 44628 KB Output is correct
29 Correct 765 ms 45088 KB Output is correct
30 Correct 805 ms 45276 KB Output is correct
31 Correct 707 ms 45448 KB Output is correct
32 Correct 707 ms 45612 KB Output is correct