Submission #446157

#	Time	Username	Problem	Language	Result	Execution time	Memory
446157		arnold518	Distributing Candies (IOI21_candies)	C++17	0 / 100	148 ms	14436 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const ll INF = 1e18;

struct Query
{
    int l, r, v;
};

int N, QQ, Q;
int A[MAXN+10];
Query BB[MAXN+10], B[MAXN+10];
int ans[MAXN+10];

ll P[MAXN+10];
ll T[MAXN+10];

vector<int> distribute_candies(vector<int> _C, vector<int> _L, vector<int> _R, vector<int> _V)
{
    N=_C.size(); Q=_L.size();
    for(int i=1; i<=N; i++) A[i]=_C[i-1];
    for(int i=1; i<=Q; i++) BB[i]={_L[i-1], _R[i-1], _V[i-1]};

    QQ=1;
    for(int i=1; i<=Q; i++)
    {
        if(i==1 || (B[QQ].v>0 && BB[i].v>0) || (B[QQ].v<0 && BB[i].v<0)) B[QQ].v+=BB[i].v;
        else B[++QQ].v=BB[i].v;
    }
    Q=QQ;

    if(Q==1)
    {
        if(B[1].v>0)
        {
            for(int i=1; i<=N; i++) ans[i]=min(A[i], B[1].v);
        }
        return vector<int>(ans+1, ans+N+1);
    }

    for(int i=Q; i>=1; i--) P[i]=P[i+1]+B[i].v;
    for(int i=1; i<=Q; i++) T[i]=INF;

    ll p=0, q=0;

    for(int i=Q; i>=1; i--)
    {
        if(B[i].v>0)
        {
            if(P[i]>p)
            {
                T[i]=max(0ll, P[i]-q);
            }
            p=max(p, P[i]);
        }
        else if(B[i].v<0)
        {
            if(P[i]<q)
            {
                T[i]=max(0ll, p-P[i]);
            }
            q=min(q, P[i]);
        }
    }

    vector<pll> V, V2;
    for(int i=1; i<=Q; i++) V.push_back({T[i], i});
    sort(V.begin(), V.end());

    for(int i=1; i<=N; i++) V2.push_back({A[i], i});
    sort(V2.begin(), V2.end());
    
    int pos=Q+1;
    for(int i=0, j=0; i<V2.size(); i++)
    {
        for(; j<V.size() && V[j].first<=V2[i].first; j++)
        {
            pos=min(pos, (int)V[j].second);
        }
        //printf("%d -> %d\n", V2[i].second, pos);
        if(pos==Q+1) ans[V2[i].second]=0;
        else if(B[pos].v>=0) ans[V2[i].second]=P[pos];
        else ans[V2[i].second]=V2[i].first+P[pos];
    }

    return vector<int>(ans+1, ans+N+1);
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:81:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=0, j=0; i<V2.size(); i++)
      |                       ~^~~~~~~~~~
candies.cpp:83:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(; j<V.size() && V[j].first<=V2[i].first; j++)
      |               ~^~~~~~~~~

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