oj.uz

Submission #813428

# Submission time Handle Problem Language Result Execution time Memory
813428 2023-08-07T17:49:15 Z Ozy Distributing Candies (IOI21_candies) C++17
100 / 100
 1471 ms 57392 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 8 ms 5460 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1317 ms 52624 KB Output is correct
2 Correct 1354 ms 55476 KB Output is correct
3 Correct 1300 ms 55468 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 325 ms 47624 KB Output is correct
3 Correct 347 ms 9964 KB Output is correct
4 Correct 1246 ms 52544 KB Output is correct
5 Correct 1288 ms 52828 KB Output is correct
6 Correct 1317 ms 52796 KB Output is correct
7 Correct 1299 ms 52896 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 5012 KB Output is correct
3 Correct 126 ms 45120 KB Output is correct
4 Correct 329 ms 9800 KB Output is correct
5 Correct 1006 ms 51344 KB Output is correct
6 Correct 946 ms 51312 KB Output is correct
7 Correct 918 ms 51348 KB Output is correct
8 Correct 1094 ms 51248 KB Output is correct
9 Correct 997 ms 51368 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 8 ms 5460 KB Output is correct
6 Correct 1317 ms 52624 KB Output is correct
7 Correct 1354 ms 55476 KB Output is correct
8 Correct 1300 ms 55468 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 325 ms 47624 KB Output is correct
11 Correct 347 ms 9964 KB Output is correct
12 Correct 1246 ms 52544 KB Output is correct
13 Correct 1288 ms 52828 KB Output is correct
14 Correct 1317 ms 52796 KB Output is correct
15 Correct 1299 ms 52896 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 5012 KB Output is correct
18 Correct 126 ms 45120 KB Output is correct
19 Correct 329 ms 9800 KB Output is correct
20 Correct 1006 ms 51344 KB Output is correct
21 Correct 946 ms 51312 KB Output is correct
22 Correct 918 ms 51348 KB Output is correct
23 Correct 1094 ms 51248 KB Output is correct
24 Correct 997 ms 51368 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 341 ms 9724 KB Output is correct
27 Correct 310 ms 49948 KB Output is correct
28 Correct 1422 ms 56596 KB Output is correct
29 Correct 1471 ms 56948 KB Output is correct
30 Correct 1439 ms 57136 KB Output is correct
31 Correct 1413 ms 57340 KB Output is correct
32 Correct 1341 ms 57392 KB Output is correct