Submission #813428

#	Time	Username	Problem	Language	Result	Execution time	Memory
813428		Ozy	Distributing Candies (IOI21_candies)	C++17	100 / 100	1471 ms	57392 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#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 pll pair<lli,lli>

#define INF (1ll<<60)
#define MAX 200000
//para el pll de last
#define p first
#define in second
//para el sweepline
#define p_arbol first 
#define tipo second

struct x {
    lli g_v;
    lli g_id;
    lli ch_v;
    lli ch_id;
    lli dif;
    lli lazy;
    lli sum;
};

lli n,offset;
x stree[MAX*4];
x trash = {-INF,0,INF,0,0,0,0};
vector<int> res,valor;
vector<pll> spline[MAX+2];

void push(lli pos) { //correcto
    if (stree[pos].lazy == 0) return;

    stree[pos].ch_v += stree[pos].lazy;
    stree[pos].g_v += stree[pos].lazy;

    if (pos < offset) {
        stree[pos*2].lazy += stree[pos].lazy;
        stree[pos*2+1].lazy += stree[pos].lazy;
    } 
    stree[pos].lazy  = 0;
    return;
}

x mergea(x izq, x der){ //revisado
    if (izq.ch_v < der.ch_v) {
        der.ch_v = izq.ch_v;
        der.ch_id = izq.ch_id;
    }
    if (izq.g_v > der.g_v) {
        der.g_v = izq.g_v;
        der.g_id = izq.g_id;
    }

    der.sum += izq.sum;
    der.dif = der.g_v - der.ch_v;
    return der;
}

x query(lli pos, lli ini, lli fin, lli l, lli r) { //correcto
    if (l > r) trash;
    
    push(pos);

    if (ini > r || fin < l) return trash;
    if (l <= ini && fin <= r) return stree[pos];

    lli mitad = (ini+fin)/2;

    x a = query(pos*2,ini,mitad,l,r);
    x b = query(pos*2+1,mitad+1,fin,l,r);
    return mergea(a,b);
}

void pushea(lli pos, lli ini, lli fin, lli l, lli r, lli pp) {
    if (l > r) return;
    push(pos);

    if (ini > r || fin < l) return;
    if (l <= ini && fin <= r) {
        stree[pos].lazy = pp;
        push(pos);
        return;
    }

    lli mitad = (ini+fin)/2;

    pushea(pos*2,ini,mitad,l,r,pp);
    pushea(pos*2+1,mitad+1,fin,l,r,pp);
    stree[pos] = mergea(stree[pos*2], stree[pos*2+1]);
}

void update(lli pos, lli s) {
    while (pos > 0) {
        stree[pos].sum += s;
        pos /= 2;
    }
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> VA) {
    swap(valor,VA);

    n = valor.size();
    offset = 1;
    while (offset < (n+1)) offset *= 2;

    rep(i,0,n-1) {
        spline[l[i]].push_back({i,1});
        spline[r[i]+1].push_back({i,0});
    }
    rep(i,0,offset-1) stree[offset+i] = {0,i,0,i,0,0,0};
    repa(i,offset-1,1) stree[i] = mergea(stree[i*2], stree[i*2+1]);


    res.resize(c.size());
    rep(i,0,c.size()-1) {

        //actualizo mi arbol
        for (auto act : spline[i]) {
            act.p_arbol++;
            if (act.tipo == 1) {
                pushea(1,0,offset-1,act.p_arbol,offset-1,valor[act.p_arbol-1]);
                update(offset+act.p_arbol,valor[act.p_arbol-1]);
            } 
            else {
                pushea(1,0,offset-1,act.p_arbol,offset-1,-valor[act.p_arbol-1]);
                update(offset+act.p_arbol,-valor[act.p_arbol-1]);
            }
        }

        //rep(i,1,7) {
        //    debugsl(i);
        //    debugsl(stree[i].g_v);
        //    debugsl(stree[i].g_id);
        //    debugsl(stree[i].ch_v);
        //    debugsl(stree[i].ch_id);
        //    debug(stree[i].sum);
        //}

        lli act = c[i];
        lli ini = 0;
        lli mitad,fin = n;
        pll last = {-1,0};

        while (ini <= fin) {
            mitad = (ini+fin)/2;
            x w = query(1,0,offset-1,mitad,offset-1);

            //debugsl(mitad);
            //debugsl(w.dif);
            //debugsl(w.g_v);
            //debug(w.ch_v);

            if(w.dif >= act) {
                //debugsl(w.g_id);
                //debug(w.ch_id);

                if (w.g_id > w.ch_id) {
                    last.in = act;
                    last.p = w.g_id;
                }
                else {
                    last.p = w.ch_id;
                    last.in = 0;
                }
                ini = mitad+1;
            }
            else fin = mitad - 1;
        }

        //debugsl(last.p);
        //debug(last.in);
        //cout << endl;

        if (last.p < 0) {
            last.p = stree[1].ch_id;
            last.in = 0;
        }

        res[i] = last.in + stree[1].sum;
        res[i] -= query(1,0,offset-1,0,last.p).sum;
    }

    return res;
}

Compilation message (stderr)

candies.cpp: In function 'x query(long long int, long long int, long long int, long long int, long long int)':
candies.cpp:66:16: warning: statement has no effect [-Wunused-value]
   66 |     if (l > r) trash;
      |                ^~~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:7:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i,a,b) for(int i = (a); i <= (b); i++)
      |                                       ^
candies.cpp:121:5: note: in expansion of macro 'rep'
  121 |     rep(i,0,c.size()-1) {
      |     ^~~

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