Submission #293381

#	Time	Username	Problem	Language	Result	Execution time	Memory
293381		Ozy	Seats (IOI18_seats)	C++17	33 / 100	558 ms	62088 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 fin;
    int minimo;
    int cantmin;
};

vector<x> ST;
int id[1000002],arr[1000002];
int base,n;
bool subtask;

void imprime(int pos) {
    cout << pos << " " << ST[pos].cantmin  << " " << ST[pos].minimo << " " << ST[pos].fin << endl;
}

void mezcla(int nodo) {
    int hizq, hder, dif;

    hizq = nodo*2;
    hder = (nodo*2)+1;

    dif = ST[hizq].minimo - (ST[hder].minimo + ST[hizq].fin);
    if (dif == 0) {
        ST[nodo].cantmin = ST[hizq].cantmin + ST[hder].cantmin;
        ST[nodo].minimo = ST[hizq].minimo;
        ST[nodo].fin = ST[hizq].fin + ST[hder].fin;
    }
    else if (dif > 0) {
        ST[nodo].cantmin = ST[hder].cantmin;
        ST[nodo].minimo = ST[hizq].fin + ST[hder].minimo;
        ST[nodo].fin = ST[hizq].fin + ST[hder].fin;
    }
    else {
        ST[nodo].cantmin = ST[hizq].cantmin;
        ST[nodo].minimo = ST[hizq].minimo;
        ST[nodo].fin = ST[hizq].fin + ST[hder].fin;
    }



}

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

    if (H == 1) {
        subtask = true;

        base = 1;
        n = H*W;
        while (base < n) base*=2;
        ST.resize(base*2);

        rep(i,0,n) arr[i] = n+1;
        rep(i,0,n-1) {

            id[i] = C[i];
            arr[C[i]] = i;

            if (C[i] == 0) {
                if (arr[C[i]] > arr[C[i]+1]) ST[base+i] = {0,0,1};
                else ST[base+i] = {2,2,1};
            }
            else if (C[i] == n-1) {
                if (arr[C[i]] > arr[C[i]-1]) ST[base+i] = {0,0,1};
                else ST[base+i] = {2,2,1};
            }
            else {
                if (arr[C[i]] > arr[C[i]-1] && arr[C[i]] > arr[C[i]+1]) ST[base+i] = {-2,-2,1};
                else if (arr[C[i]] < arr[C[i]-1] && arr[C[i]] < arr[C[i]+1]) ST[base+i] = {2,2,1};
                else ST[base+i] = {0,0,1};
            }

        }

        for (int j = base-1; j > 0; j--) mezcla(j);

    }

}

void checa(int pos) {

    if (pos >= n || pos < 0) return;

    if (pos == 0) {
        if (arr[pos] > arr[pos+1]) ST[base + arr[pos]] = {0,0,1};
        else ST[base + arr[pos]] = {2,2,1};
    }
    else if (pos == n-1) {
        if (arr[pos] > arr[pos-1]) ST[base + arr[pos]] = {0,0,1};
        else ST[base + arr[pos]] = {2,2,1};
    }
    else {
        if (arr[pos] > arr[pos-1] && arr[pos] > arr[pos+1]) ST[base + arr[pos]] = {-2,-2,1};
        else if (arr[pos] < arr[pos-1] && arr[pos] < arr[pos+1]) ST[base + arr[pos]] = {2,2,1};
        else ST[base + arr[pos]] = {0,0,1};
    }

    pos = base + arr[pos];
    pos >>= 1;

    while (pos > 0) {
        mezcla(pos);
        pos >>= 1;
    }

}

int swap_seats(int a, int b) {

    if(subtask) {
        swap(arr[id[a]], arr[id[b]]);
        swap(id[a], id[b]);

        checa(id[a]-1);
        checa(id[a]);
        checa(id[a]+1);
        checa(id[b]-1);
        checa(id[b]);
        checa(id[b]+1);


        return ST[1].cantmin;
    }

    return 2;
}

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