Submission #446678

#	Time	Username	Problem	Language	Result	Execution time	Memory
446678		arnold518	Distributing Candies (IOI21_candies)	C++17	0 / 100	380 ms	70452 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];

struct Node
{
    ll val, maxv, minv;
    Node() : val(0), maxv(0), minv(0) {}
};

Node operator + (const Node &p, const Node &q)
{
    Node ret;
    ret.maxv=max(p.maxv, q.maxv);
    ret.minv=min(p.minv, q.minv);
    ret.val=max({p.val, q.val, p.maxv-q.minv, q.maxv-p.minv});
    return ret;
}

struct SEG
{
    Node tree[MAXN*4+10];
    ll lazy[MAXN*4+10];

    void busy(int node, int tl, int tr)
    {
        if(lazy[node]==0) return;
        tree[node].maxv+=lazy[node];
        tree[node].minv+=lazy[node];
        if(tl!=tr)
        {
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node]=0;
        return;
    }

    void update(int node, int tl, int tr, int l, int r, ll k)
    {
        busy(node, tl, tr);
        if(l<=tl && tr<=r)
        {
            lazy[node]+=k;
            busy(node, tl, tr);
            return;
        }
        if(r<tl || tr<l) return;
        int mid=tl+tr>>1;
        update(node*2, tl, mid, l, r, k);
        update(node*2+1, mid+1, tr, l, r, k);
        tree[node]=tree[node*2]+tree[node*2+1];
    }

    int query(int node, int tl, int tr, ll k, Node p)
    {
        if(tl==tr)
        {
            Node t;
            if(p.val<0) t=tree[node];
            else t=p+tree[node];
            if(t.val<=k) return tl;
            return tl+1;
        }
        int mid=tl+tr>>1;
        busy(node, tl, tr);
        busy(node*2, tl, mid);
        busy(node*2+1, mid+1, tr);
        Node t;
        if(p.val<0) t=tree[node*2+1];
        else t=tree[node*2+1]+p;
        if(t.val<=k) return query(node*2, tl, mid, k, t);
        else return query(node*2+1, mid+1, tr, k, p);
    }

    ll get(int node, int tl, int tr, int p)
    {
        busy(node, tl, tr);
        if(tl==tr) return tree[node].minv;
        int mid=tl+tr>>1;
        if(p<=mid) return get(node*2, tl, mid, p);
        else return get(node*2+1, mid+1, tr, p);
    }
}seg;

ll S[MAXN+10], P[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]+1, _R[i-1]+1, _V[i-1]};

    vector<pii> V;
    for(int i=1; i<=Q; i++)
    {
        V.push_back({B[i].l, i});
        V.push_back({B[i].r+1, -i});
    }
    sort(V.begin(), V.end());

    ll sum=0;
    set<int> SS;
    for(int i=1, j=0; i<=N; i++)
    {
        for(; j<V.size() && V[j].first<=i; j++)
        {
            int t=V[j].second;
            if(t>0)
            {
                for(int k=t; k<=Q; k++) S[k]+=B[t].v;
                P[t]+=B[t].v;
                sum+=B[t].v;
                SS.insert(t);
            }
            else
            {
                for(int k=-t; k<=Q; k++) S[k]+=-B[-t].v;
                P[t]+=-B[-t].v;
                sum+=-B[-t].v;
                SS.erase(-t);
            }
        }
        ll minv=sum, maxv=sum;
        for(int k=Q; k>=0; k--)
        {
            if(P[k]==0) continue;
            minv=min(minv, S[k]);
            maxv=max(maxv, S[k]);
            if(maxv-minv>A[i]) break;
            auto it=SS.upper_bound(k);
            if(k==0 || it==SS.end() || (B[*it].v>0 && P[k]<0) || (B[*it].v<0 && P[k]>0))
            {
                //printf("%d\n", k);
                if(S[k]==minv) ans[i]=sum-S[k];
                else if(S[k]==maxv) ans[i]=A[i]-(S[k]-sum);
            }
        }
    }
    return vector<int>(ans+1, ans+N+1);

    sum=0;
    for(int i=1, j=0; i<=N; i++)
    {
        for(; j<V.size() && V[j].first<=i; j++)
        {
            int t=V[j].second;
            if(t>0)
            {
                seg.update(1, 0, Q, t, Q, B[t].v);
                sum+=B[t].v;
            }
            else
            {
                seg.update(1, 0, Q, -t, Q, -B[-t].v);
                sum+=-B[-t].v;
            }
        }
        Node t;
        t.val=-1;
        int pos=seg.query(1, 0, Q, A[i], t);
        printf("%d\n", pos);
    }

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

Compilation message (stderr)

candies.cpp: In member function 'void SEG::update(int, int, int, int, int, ll)':
candies.cpp:66:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         int mid=tl+tr>>1;
      |                 ~~^~~
candies.cpp: In member function 'int SEG::query(int, int, int, ll, Node)':
candies.cpp:82:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |         int mid=tl+tr>>1;
      |                 ~~^~~
candies.cpp: In member function 'll SEG::get(int, int, int, int)':
candies.cpp:97:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |         int mid=tl+tr>>1;
      |                 ~~^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:123:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for(; j<V.size() && V[j].first<=i; j++)
      |               ~^~~~~~~~~
candies.cpp:162:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |         for(; j<V.size() && V[j].first<=i; j++)
      |               ~^~~~~~~~~

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