답안 #795863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
795863 2023-07-27T18:15:50 Z amin 사탕 분배 (IOI21_candies) C++17
0 / 100
671 ms 36752 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;
void update(int v,int tl,int tr,int pos)
{
    if(pos>tr||pos<tl)
        return ;
    if(tl==tr)
    {
        masuf[v]=max(o,a[pos]);
        misuf[v]=min(o,a[pos]);
        sum[v]=a[pos];
        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];
    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],tl}};
    }
    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],tl}};
    }
    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]==0)
             {
                 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=getmin(1,0,q-1,m,q-1).second.first;
             ll ma=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)
        {
            ans.push_back(0);
            continue;
        }
         en=getmax(1,0,q-1,r,q-1).second.second;
if(en==r&&getmax(1,0,q-1,r,q-1).second.first==get(1,0,q-1,r,q-1))
    en--;
ans.push_back(get(1,0,q-1,en+1,q-1));
    }
    if(a[l]>0)
    {
        if(r==q)
        {
            ans.push_back(c[i]);
            continue;
        }
        en=getmin(1,0,q-1,r,q-1).second.second;
     //   cout<<en<<' ';
if(en==r&&getmin(1,0,q-1,r,q-1).second.first==get(1,0,q-1,r,q-1))
    en--;
  //  cout<<en<<' ';

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


     }
     return ans;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 312 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 671 ms 36752 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 80 ms 23372 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 312 KB Output isn't correct
3 Halted 0 ms 0 KB -