Submission #435030

#	Time	Username	Problem	Language	Result	Execution time	Memory
435030		Enkognit	Distributing Candies (IOI21_candies)	C++17	29 / 100	2068 ms	54068 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fi first
#define se second

ll n, m, q;

pll d[1000001];
ll tt[1000001];

void build(int h,int l,int r)
{
    if (l==r)
    {
        d[h]=mp(0, 0);
        return;
    }
    int w=(l+r)/2;
    build(h*2,l,w);
    build(h*2+1,w+1,r);
    d[h]=mp(0, 0);
}

void push(int h)
{
    if (tt[h])
    {
        d[h*2].fi+=tt[h];
        d[h*2].se+=tt[h];
        d[h*2+1].fi+=tt[h];
        d[h*2+1].se+=tt[h];
        tt[h*2]+=tt[h];
        tt[h*2+1]+=tt[h];
        tt[h]=0;
    }
}

void update(int h,int l,int r,int x,int y,int k)
{
    if (x>y) return;
    if (l==x && y==r)
    {
        d[h].fi+=k;
        d[h].se+=k;
        tt[h]+=k;
        return;
    }
    push(h);
    int w=(l+r)/2;
    update(h*2,l,w,x,min(y,w),k);
    update(h*2+1,w+1,r,max(x,w+1),y,k);
    d[h].fi=min(d[h*2].fi,d[h*2+1].fi);
    d[h].se=max(d[h*2].se,d[h*2+1].se);
}

ll get_min(int h,int l,int r,int x,int y)
{
    if (x>y) return 1e18;
    if (l==x && y==r) return d[h].fi;
    int w=(l+r)/2;
    push(h);
    return min(get_min(h*2,l,w,x,min(y,w)), get_min(h*2+1,w+1,r,max(x,w+1),y));
}

ll get_max(int h,int l,int r,int x,int y)
{
    if (x>y) return -1e18;
    if (l==x && y==r) return d[h].se;
    int w=(l+r)/2;
    push(h);
    return max(get_max(h*2,l,w,x,min(y,w)), get_max(h*2+1,w+1,r,max(x,w+1),y));
}

ll get(int h,int l,int r,int x)
{
    if (l==r)
    {
        return d[h].fi;
    }
    int w=(l+r)/2;
    if (x<=w) return get(h*2,l,w,x); else return get(h*2+1,w+1,r,x);
}

vector<pll> gg[1000001];

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {

    n=c.size();
    q=l.size();

    for (int i = 0; i < q; i++)
    {
        gg[l[i]].pb(mp(i, v[i]));
        gg[r[i]+1].pb(mp(i, -v[i]));
    }

    vector<int> ans;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < gg[i].size(); j++)
        {
            update(1,0,q,gg[i][j].fi+1,q,gg[i][j].se);
        }

        //cout << i << " " << d[1].fi << " " << d[1].se << "\n";

        if (d[1].se-d[1].fi<c[i])
        {
            ans.pb(get(1,0,q,q)-get_min(1,0,q,0,q));
            continue;
        }

        ll l=0, r=q;
        while (l<r)
        {
            int w=(l+r+1)/2;
            if (get_max(1,0,q,w,q)-get_min(1,0,q,w,q)>=c[i]) l=w; else r=w-1;
        }

        //cout << i << " :\n";
        //cout << " l : " << l << "\n";

        ll o1=get(1,0,q,l), o2=get(1,0,q,q);
        //cout << " " << o1 << "\n";
        //cout << " " << o2 << "\n";
        assert(o1!=o2);
        if (o1<o2)
        {
            ll o3=get_max(1,0,q,l+1,q);
            ans.pb(c[i]-(o3-o2));
        }else
        {
            ll o3=get_min(1,0,q,l+1,q);
            ans.pb(o2-o3);
        }
    }

    return ans;
}

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:110:27: 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]
  110 |         for (int j = 0; j < gg[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~

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