답안 #896756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
896756 2024-01-02T05:28:28 Z Muhammad_Aneeq 사탕 분배 (IOI21_candies) C++17
11 / 100
5000 ms 10604 KB
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
int const N=2e5+10;
int n;
struct Seg
{
    int lazy=0,mis=0,mas=0,mif=0,maf=0;    
};
Seg St[4*N]={};int a[N]={};
void build(int i,int st,int en)
{
    if (st==en)
    {
        St[i].mis=St[i].mas=a[st];
        St[i].mif=St[i].maf=0;
        return;
    }
    int mid=(st+en)/2;
    build(i*2,st,mid);build(i*2+1,mid+1,en);
    St[i].mis=min(St[i*2].mis,St[i*2+1].mis);St[i].mas=max(St[i*2].mas,St[i*2+1].mas);
    St[i].mif=min(St[i*2].mif,St[i*2+1].mif);St[i].maf=max(St[i*2].maf,St[i*2+1].maf);
}
void update(int i,int st,int en,long long val)
{
    if (val==0)
        return;
    if (val>0)
        val=min(val,1ll*St[i].mas);
    if (val<0)
        val=-min(abs(val),1ll*St[i].maf);
    if (St[i].mis==St[i].mas)
    {
        if (val>0)
        {
            int x=min(1ll*St[i].mis,val);
            St[i].lazy+=x;
            St[i].mis-=x;St[i].mas-=x;
            St[i].maf+=x;St[i].mif+=x;
            return;
        }
    }
    if (St[i].mif==St[i].maf)
    {
        if (val<0)
        {
            int x=min(1ll*St[i].mif,abs(val));
            x=-x;
            St[i].lazy+=x;
            St[i].mis-=x;St[i].mas-=x;
            St[i].maf+=x;St[i].mif+=x;
            return;
        }
    }
    if (val>0)
    {
        if (St[i].mas==0)
            return;
        if (St[i].mis>=val)
        {
            St[i].lazy+=val;
            St[i].mis-=val;St[i].mas-=val;
            St[i].mif+=val;St[i].maf+=val;
            return;
        }
    }
    if (val<0)
    {
        if (St[i].maf==0)
            return;
        if (St[i].mif>=abs(val))
        {
            St[i].lazy+=val;
            St[i].mis-=val;St[i].mas-=val;
            St[i].mif+=val;St[i].maf+=val;
            return;
        }
    }
    int mid=(st+en)/2;
    update(i*2,st,mid,val+St[i].lazy);update(i*2+1,mid+1,en,val+St[i].lazy);
    St[i].lazy=0;
    St[i].mis=min(St[i*2].mis,St[i*2+1].mis);St[i].mas=max(St[i*2].mas,St[i*2+1].mas);
    St[i].mif=min(St[i*2].mif,St[i*2+1].mif);St[i].maf=max(St[i*2].maf,St[i*2+1].maf);
}
void update1(int i,int st,int en,long long val=0)
{
    if (st==en)
    {
        St[i].mif+=val;
        return;
    }
    int mid=(st+en)/2;
    update1(i*2,st,mid,val+St[i].lazy);update1(i*2+1,mid+1,en,val+St[i].lazy);
}
int get(int i,int r,int st,int en)
{
    if (st==en)
        return St[i].mif;
    int mid=(st+en)/2;
    if (r<=mid)
        return get(i*2,r,st,mid);
    return get(i*2+1,r,mid+1,en);
}
vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v)
{
    n=c.size();
    bool w=0;
    for (auto i:v)
        if (i<0)
            w=1;
    bool subtask_4=1;
    for (int i=0;i<l.size();i++)
    {
        if (l[i]!=0||r[i]!=n-1)
            subtask_4=0;
    }
    if (subtask_4)
    {
        map<int,vector<int>>d;
        for (int i=0;i<n;i++)
        {
            a[i]=c[i];
            d[a[i]].push_back(i);
        }
        sort(a,a+n);
        build(1,0,n-1);
        long long x=0;
        for (auto i:v)
        {
            if (i>0&&x>=0)
                x+=i;
            else if (i<0&&x<=0)
                x+=i;
            else
            {
                update(1,0,n-1,x);
                x=i;
            }
        }
        update(1,0,n-1,x);
        update1(1,0,n-1);
        vector<int>ans(n,0);
        for (int i=0;i<n;i++)
        {
            ans[d[a[i]].back()]=get(1,i,0,n-1);
            d[a[i]].pop_back();
        }
        return ans;
    }
    if (w==0)
    {
        vector<long long>d(n+1,0);
        for (int i=0;i<l.size();i++)
        {
            d[l[i]]+=v[i];
            d[r[i]+1]-=v[i];
        }
        vector<long long>ans;
        ans.push_back(d[0]);
        for (int i=1;i<n;i++)
            ans.push_back(d[i]+ans.back());
        for (int i=0;i<n;i++)
        {
            ans[i]=(ans[i]<0?0:ans[i]);
            ans[i]=min(1ll*c[i],ans[i]);
        }
        vector<int>g;
        g={begin(ans),end(ans)};
        return g;
    }
    vector<long long>ans(n,0);
    for (int i=0;i<l.size();i++)
    {
        for (int j=l[i];j<=r[i];j++)
        {
            ans[j]+=v[i];
            ans[j]=min(ans[j],1ll*c[j]);
            ans[j]=(ans[j]<0?0:ans[j]);
        }
    }
    vector<int>g={begin(ans),end(ans)};
    return g;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for (int i=0;i<l.size();i++)
      |                  ~^~~~~~~~~
candies.cpp:155:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         for (int i=0;i<l.size();i++)
      |                      ~^~~~~~~~~
candies.cpp:174:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     for (int i=0;i<l.size();i++)
      |                  ~^~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 10440 KB Output is correct
2 Correct 74 ms 10544 KB Output is correct
3 Correct 73 ms 10604 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 424 KB Output is correct
2 Correct 169 ms 5096 KB Output is correct
3 Correct 174 ms 4176 KB Output is correct
4 Execution timed out 5031 ms 8016 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 2203 ms 5616 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 74 ms 10440 KB Output is correct
7 Correct 74 ms 10544 KB Output is correct
8 Correct 73 ms 10604 KB Output is correct
9 Correct 0 ms 424 KB Output is correct
10 Correct 169 ms 5096 KB Output is correct
11 Correct 174 ms 4176 KB Output is correct
12 Execution timed out 5031 ms 8016 KB Time limit exceeded
13 Halted 0 ms 0 KB -