Submission #288478

#	Time	Username	Problem	Language	Result	Execution time	Memory
288478		Ozy	Seats (IOI18_seats)	C++17	31 / 100	4101 ms	87928 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];
int mif, maf, mic, mac;

void dd(x nodo){
    debug(nodo.MAXf);
    debug(nodo.MINf);
    debug(nodo.MAXc);
    debug(nodo.MINc);
    debug(nodo.hizq);
    debug(nodo.hder);
    debug(" ");
}

void d(int p){
    x nodo;
    debug(p);
    nodo = ST[p];
    dd(nodo);
}

void h(int pos){

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

}

void crea(int ini, int fin, int num, int r, int c, int pos) {
    int mitad;

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

        ST[pos].MAXf = r;
        ST[pos].MAXc = c;
        ST[pos].MINf = r;
        ST[pos].MINc = c;

        return;
    }
    else if (ini <= num && fin >= num) {

        mitad = (ini+fin) / 2;

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

        crea(ini, mitad, num, r, c, ST[pos].hizq);
        crea(mitad + 1, fin, num, r, c, 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;

    }
    return;

}

void query(int nodo, int ini, int fin, int r) {
    int mitad;

    if (fin <= r) {

        mif = min(mif, ST[nodo].MINf);
        maf = max(maf, ST[nodo].MAXf);
        mic = min(mic, ST[nodo].MINc);
        mac = max(mac, ST[nodo].MAXc);

        return;
    }
    else if (ini <= r) {

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

        return;

    }
    return;
}

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

    l1 = maf - mif + 1;
    l2 = mac - mic + 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]};
        crea(0, n-1, i, R[i], C[i], 1);
    }

}

int swap_seats(int a, int b) {

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

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


    p = 0;
    res = 0;

    while (p < n) {

        mif = INT_MAX;
        maf = 0;
        mic = INT_MAX;
        mac = 0;

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

        if (checa(p)) {
            res++;
            p++;
        }
        else {
            p = max(p + 1, (maf - mif + 1) * (mac - mic + 1) - 1);
        }

    }

    return res;

}

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