Submission #446712

#	Time	Username	Problem	Language	Result	Execution time	Memory
446712		arnold518	Distributing Candies (IOI21_candies)	C++17	100 / 100	763 ms	42920 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-1;
            return tl;
        }
        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);
    }

    Node get2(int node, int tl, int tr, int l, int r)
    {
        if(l<=tl && tr<=r) return tree[node];
        int mid=tl+tr>>1;
        if(r<=mid) return get2(node*2, tl, mid, l, r);
        if(mid+1<=l) return get2(node*2+1, mid+1, tr, l, r);
        return get2(node*2, tl, mid, l, mid)+get2(node*2+1, mid+1, tr, mid+1, r);
    }
}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;
    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);
        Node node=seg.get2(1, 0, Q, pos, Q);
        ll val;
        if(pos==-1) val=A[i];
        else val=seg.get(1, 0, Q, pos);
        
        if(pos==-1)
        {
            node.maxv=max(node.maxv, (ll)A[i]);   
        }
        if(val==node.maxv) ans[i]=sum-node.minv;
        else if(val==node.minv) ans[i]=A[i]-(node.maxv-sum);
    }

    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 member function 'Node SEG::get2(int, int, int, int, int)':
candies.cpp:105:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |         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:131: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]
  131 |         for(; j<V.size() && V[j].first<=i; j++)
      |               ~^~~~~~~~~

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