Submission #287796

#	Time	Username	Problem	Language	Result	Execution time	Memory
287796		Ozy	Seats (IOI18_seats)	C++17	0 / 100	4096 ms	39872 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 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(a.MAXf, b.MAXf);
        ST[pos].MINf = max(a.MINf, b.MINf);
        ST[pos].MAXc = max(a.MAXc, b.MAXc);
        ST[pos].MINc = max(a.MINc, b.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,(H*W)-1) {

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

        uso = {R[i],R[i],C[i],C[i],0,0};
        uso = crea(0,(H*W)-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,a,uso,1);

    uso = {id[b].fil, id[b].fil, id[b].col, id[b].col,0,0};
    crea(0,n-1,b,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);

    }

    return res;

}

Compilation message (stderr)

seats.cpp: In function 'x crea(int, int, int, x, int)':
seats.cpp:50:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   50 |         if (ST[pos].hizq = 0) h(pos);
      |             ~~~~~~~~~~~~~^~~

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