oj.uz

Submission #1053027

# Submission time Handle Problem Language Result Execution time Memory
1053027 2024-08-11T08:02:06 Z Huseyn123 Distributing Candies (IOI21_candies) C++17
40 / 100
 68 ms 20052 KB 
#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]];
                    }
                }
                if(val[e[l][1]]+res>c[i]){
                    res=c[i]-val[e[l][1]];
                }
                if(val[e[l][2]]+res<0){
                    res=-val[e[l][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.0 / 3.0

# Verdict Execution time Memory 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 1 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 13660 KB Output is correct
2 Correct 53 ms 12980 KB Output is correct
3 Correct 54 ms 12880 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 32 ms 15840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 34 ms 14324 KB Output is correct
4 Correct 27 ms 3676 KB Output is correct
5 Correct 55 ms 18780 KB Output is correct
6 Correct 68 ms 19360 KB Output is correct
7 Correct 59 ms 20052 KB Output is correct
8 Correct 60 ms 18708 KB Output is correct
9 Correct 52 ms 13908 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory 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 1 ms 348 KB Output is correct
6 Correct 59 ms 13660 KB Output is correct
7 Correct 53 ms 12980 KB Output is correct
8 Correct 54 ms 12880 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 32 ms 15840 KB Output isn't correct
11 Halted 0 ms 0 KB -