제출 #1054701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1054701		Huseyn123	사탕 분배 (IOI21_candies)	C++17	11 / 100	59 ms	15948 KiB

candies

    #include "candies.h"
    #include <bits/stdc++.h>
    #include <vector>
    using namespace std;
    typedef long long ll;
    vector<array<ll,3>> e;
    vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
        int n = c.size();
        int q = l.size();
        vector<int> s(n);
        bool ok=true;
        for(int i=0;i<q;i++){
            if(v[i]<0){
                ok=false; 
            }
        }
        if(n<=2000 && q<=2000){
            for(int i=0;i<q;i++){
                for(int j=l[i];j<=r[i];j++){
                    s[j]+=v[i];
                    s[j]=max(s[j],0);
                    s[j]=min(s[j],c[j]);
                }
            }
        }
        else if(ok){
            long long sum[n+2];
            for(int i=0;i<=n+1;i++){
                sum[i]=0;
            }
            for(int i=0;i<q;i++){
                sum[l[i]+1]+=v[i];
                sum[r[i]+2]-=v[i];
            }
            for(int i=1;i<=n;i++){
                sum[i]+=sum[i-1];
                s[i-1]=min(sum[i],(ll)c[i-1]);
            }
        }
        else{
            ll val[q+1];
            pair<ll,ll> mn[q+1],mx[q+1];
            val[0]=0;
            for(int i=1;i<=q;i++){
                val[i]=v[i-1];
                val[i]+=val[i-1];
            }
            mn[q]={val[q],q}; 
            mx[q]={val[q],q};
            for(int i=q-1;i>=1;i--){
                mn[i]={val[i],(ll)i};
                mx[i]={val[i],(ll)i};
                if(mn[i+1].first<=val[i]){
                    mn[i]=mn[i+1];
                }
                if(mx[i+1].first>=val[i]){
                    mx[i]=mx[i+1];
                }
            }
            int ind=1;
            while(ind<=q){
                e.push_back({mx[ind].first-mn[ind].first,mx[ind].second,mn[ind].second});
                ind=max(mx[ind].second,mn[ind].second)+1;
            }
            int sz=(int)e.size();
            for(int i=0;i<n;i++){
                int l,r,mid;
                l=0; 
                r=sz-1;
                while(l<r){
                    mid=(l+r)/2; 
                    if(e[mid][0]<c[i]){
                        r=mid;
                    }
                    else{
                        l=mid+1;
                    }
                }
                ll res=0;
                if(e[l][0]<c[i]){
                    if(l){
                        if(e[l-1][1]>e[l-1][2]){
                            res+=c[i]-val[e[l-1][1]];
                        }
                        else{
                            res-=val[e[l-1][2]];
                        }
                    }
                }
                else{
                    if(e[sz-1][1]>e[sz-1][2]){
                        res+=c[i]-val[e[sz-1][1]];
                    }
                    else{
                        res-=val[e[sz-1][2]];
                    }
                }
                s[i]=val[q]+res;
            }
        }
        return s;
    }

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33