oj.uz

Submission #609743

# Submission time Handle Problem Language Result Execution time Memory
609743 2022-07-27T20:19:34 Z Ozy Distributing Candies (IOI21_candies) C++17
0 / 100
 132 ms 27648 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 132 ms 27648 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -