Submission #609743

#	Time	Username	Problem	Language	Result	Execution time	Memory
609743		Ozy	Distributing Candies (IOI21_candies)	C++17	0 / 100	132 ms	27648 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 200000

struct x{
    lli pos;
    lli alto;
    lli bajo;
};

vector<int> res;
lli n,q,offset,apu,p,ini,fin,mitad;
x st[MAX+2],k;

vector<pair<lli,lli> > eventos;
pair<lli,lli> eve;

x mergear(x a, x b) {
    x nuevo = a;

    nuevo.pos += b.pos;
    nuevo.alto = max(nuevo.alto, b.alto+a.pos);
    nuevo.bajo = min(nuevo.bajo, b.bajo+a.pos);

    return nuevo;
}

void update(lli act) {
    st[act] = mergear(st[act*2], st[(act*2)+1]);
    update(act/2);
}

x busca(lli p, lli ini, lli fin, lli l, lli r) {

    if (ini > r || fin < l) return {0,0,0};
    else if (l <= ini && fin <= r) return st[p];

    mitad = (ini+fin)/2;
    x a = busca(p*2, ini, mitad, l, r);
    x b = busca((p*2)+1, mitad+1, fin, l , r);

    return mergear(a,b);
}

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

    n = c.size();
    res.resize(n,0);
    offset = 1;
    while (offset < n) offset *= 2;

    q = r.size();
    rep(i,0,q-1) {
        eventos.push_back({l[i],i});
        eventos.push_back({r[i]+1,i});
    }
    sort(eventos.begin(), eventos.end());

    apu = 0;
    rep(i,0,n-1) {

        while (apu < q && apu) {
            eve = eventos[apu];
            apu++;

            p = eve.second + offset;
            if (st[p].pos == 0) {
                st[p].pos = v[eve.second];
                st[p].alto = max(0,v[eve.second]);
                st[p].bajo = min(0,v[eve.second]);
            }
            else st[p] = {0,0,0};

            update(p/2);
        }

        ini = 1;
        fin = q;
        while (ini <= fin) {
            mitad = (ini + fin)/2;
            k = busca(1,1,offset,mitad,q);

            if (k.alto <= c[0] && k.bajo >= 0) {
                res[i] = k.pos;
                fin = mitad - 1;
            }
            ini = mitad+1;
        }
    }

    return res;
}

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