Submission #446193

#	Time	Username	Problem	Language	Result	Execution time	Memory
446193		arnold518	Distributing Candies (IOI21_candies)	C++17	0 / 100	155 ms	16332 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=-INF, q=INF;

    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, V3;
    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());
    
    //for(int i=1; i<=Q; i++) printf("%lld ", T[i]); printf("\n");

    ll t=0, t2=0;
    for(int i=1; i<=Q; i++)
    {
        t+=B[i].v;
        t=max(t, 0ll);
        t2=max(t2, t);
        V3.push_back({t2, i});
    }
    V3.push_back({t2, Q+1});

    int meet=0;
    priority_queue<int, vector<int>, greater<int>> PQ1, PQ2;
    for(int i=0, j=0, k=0; i<V2.size(); i++)
    {   
        for(; k<V3.size() && V3[k].first<V2[i].first; k++)
        {
            meet=max(meet, (int)V3[k].second);
            if(V3[k].first>=V2[i].first) break;
        }
        for(; j<V.size() && V[j].first<=V2[i].first; j++)
        {
            if(B[V[j].second].v>0) PQ1.push(V[j].second);
            else PQ2.push(V[j].second);
        }
        while(!PQ2.empty() && PQ2.top()<meet) PQ2.pop();
        int pos=Q+1;
        if(!PQ1.empty()) pos=min(pos, PQ1.top());
        if(!PQ2.empty()) pos=min(pos, PQ2.top());

        //printf("%d -> %d %d\n", V2[i].second, pos, meet);
        if(pos==Q+1)
        {
            if(B[Q].v<0) ans[V2[i].second]=0;
            else ans[V2[i].second]=V2[i].first;
        }
        else if(B[pos].v>=0) ans[V2[i].second]=P[pos];
        else ans[V2[i].second]=V2[i].first+P[pos];
    }

    for(int i=1; i<=N; i++)
    {
        ans[i]=max(ans[i], 0);
        ans[i]=min(ans[i], A[i]);
    }
    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:94:29: 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]
   94 |     for(int i=0, j=0, k=0; i<V2.size(); i++)
      |                            ~^~~~~~~~~~
candies.cpp:96: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]
   96 |         for(; k<V3.size() && V3[k].first<V2[i].first; k++)
      |               ~^~~~~~~~~~
candies.cpp:101: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]
  101 |         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