Submission #287806

#	Time	Username	Problem	Language	Result	Execution time	Memory
287806		Ozy	Seats (IOI18_seats)	C++17	5 / 100	4097 ms	86776 KiB

seats

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

struct x{
    int MAXf;
    int MINf;

    int MAXc;
    int MINc;

    int hizq;
    int hder;
};

struct y{
    int fil;
    int col;
};

int cont,n,p,res;
x uso,maximos;
x ST[2100000];
y id[1000002];


void d(int p){
    x nodo;
    debug(p);
    nodo = ST[p];
    debug(nodo.MAXf);
    debug(nodo.MINf);
    debug(nodo.MAXc);
    debug(nodo.MINc);
    debug(nodo.hizq);
    debug(nodo.hder);
    debug(" ");
}

void h(int pos){

    ST[pos].hizq = cont++;
    ST[pos].hder = cont++;

}

x crea(int ini, int fin, int num, x des, int pos) {
    x a,b;
    int mitad;

    if (ini == fin && ini == num) {

        ST[pos].MAXf = des.MAXf;
        ST[pos].MAXc = des.MAXc;
        ST[pos].MINf = des.MINf;
        ST[pos].MINc = des.MINc;

        return ST[pos];
    }
    else if (ini <= num && fin >= num) {

        mitad = (ini+fin) / 2;

        if (ST[pos].hizq == 0) h(pos);

        a = crea(ini, mitad, num, des, ST[pos].hizq);
        b = crea(mitad + 1, fin, num, des, ST[pos].hder);

        ST[pos].MAXf = max(ST[ST[pos].hizq].MAXf, ST[ST[pos].hder].MAXf);
        ST[pos].MINf = min(ST[ST[pos].hizq].MINf, ST[ST[pos].hder].MINf);
        ST[pos].MAXc = max(ST[ST[pos].hizq].MAXc, ST[ST[pos].hder].MAXc);
        ST[pos].MINc = min(ST[ST[pos].hizq].MINc, ST[ST[pos].hder].MINc);


        return ST[pos];

    }
    return {0, 1000002, 0, 1000002, 0, 0};

}

x query(int nodo, int ini, int fin, int r) {
    int mitad;
    x a,b;

    if (fin <= r) {

        return ST[nodo];

    }
    else if (ini <= r) {

        mitad = (ini+fin) / 2;
        a = query(ST[nodo].hizq,ini,mitad, r);
        b = query(ST[nodo].hder,mitad+1,fin, r);

        a.MAXf = max(a.MAXf, b.MAXf);
        a.MINf = min(a.MINf, b.MINf);
        a.MAXc = max(a.MAXc, b.MAXc);
        a.MINc = min(a.MINc, b.MINc);

        return a;

    }
    return {0, 1000002,0, 1000002,0,0};
}

bool checa(x act, int val) {
    int l1,l2;

    l1 = act.MAXf - act.MINf + 1;
    l2 = act.MAXc - act.MINc + 1;

    l1 *= l2;

    return (l1 == (val+1));

}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {

    n = H*W;

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

        id[i] = {R[i], C[i]};

        uso = {R[i], R[i], C[i], C[i], 0, 0};
        uso = crea(0, n-1, i, uso, 1);
    }

}

int swap_seats(int a, int b) {

    uso = {id[a].fil, id[a].fil, id[a].col, id[a].col,0,0};
    crea(0, n-1, b, uso, 1);

    uso = {id[b].fil, id[b].fil, id[b].col, id[b].col,0,0};
    crea(0, n-1, a, uso, 1);

    swap(id[a], id[b]);


    p = 0;
    maximos = {id[p].fil, id[p].fil, id[p].col, id[p].col, 0 ,0};
    res = 0;

    while (p < n) {

        maximos = query(1, 0, n-1, p);

        if (checa(maximos, p)) {
            res++;
            p++;
        }
        else {
            p = (maximos.MAXf - maximos.MINf + 1) * (maximos.MAXc - maximos.MINc + 1) - 1;
        }

    }

    return res;

}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30