Submission #446152

#	Time	Username	Problem	Language	Result	Execution time	Memory
446152		arnold518	Distributing Candies (IOI21_candies)	C++17	0 / 100	167 ms	23320 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, Q;
int A[MAXN+10];
Query 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++) B[i]={_L[i-1], _R[i-1], _V[i-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=-INF, q=INF;

    for(int i=Q+1; 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);
        }
        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:64: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]
   64 |     for(int i=0, j=0; i<V2.size(); i++)
      |                       ~^~~~~~~~~~
candies.cpp:66: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]
   66 |         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