제출 #795903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
795903		amin	사탕 분배 (IOI21_candies)	C++17	37 / 100	885 ms	44104 KiB

candies

#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);
     }
     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: 0 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33