Submission #434223

#	Time	Username	Problem	Language	Result	Execution time	Memory
434223		Tiago_Marques	Seats (IOI18_seats)	C++17	0 / 100	4067 ms	72516 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

#define REP(i, a, b) for (ll i=a; i<b; i++)

std::vector<int> r;
std::vector<int> c;
int h, w;
int segment_tree[4000000][4] = {};
set<int> beautiful;

void create (ll i, ll minimo, ll maximo)
{
    if (minimo == maximo)
    {
        segment_tree[i][0] = r[minimo];
        segment_tree[i][1] = r[minimo];
        segment_tree[i][2] = c[minimo];
        segment_tree[i][3] = c[minimo];
        return;
    }
    ll med = (minimo + maximo)/2;
    create (2*i+1, minimo, med);
    create (2*i+2, med+1, maximo);
    segment_tree[i][0] = min (segment_tree[2*i+1][0], segment_tree[2*i+2][0]);
    segment_tree[i][1] = max (segment_tree[2*i+1][1], segment_tree[2*i+2][1]);
    segment_tree[i][2] = min (segment_tree[2*i+1][2], segment_tree[2*i+2][2]);
    segment_tree[i][3] = max (segment_tree[2*i+1][3], segment_tree[2*i+2][3]);
    return;
}

void change (ll i, ll minimo, ll maximo, ll x, ll valor, ll type)
{
    if (minimo == maximo)
    {
        segment_tree[i][type] = valor;
        return;
    }
    ll med = (minimo + maximo)/2;
    if (x <= med)
        change (2*i+1, minimo, med, x, valor, type);
    else
        change(2*i+2, med+1, maximo, x, valor, type);
    if (type%2 == 0)
        segment_tree[i][type] = min(segment_tree[2*i+1][type], segment_tree[2*i+2][type]);
    else
        segment_tree[i][type] = max(segment_tree[2*i+1][type], segment_tree[2*i+2][type]);
}

ll intervalo (ll i, ll minimo, ll maximo, ll menor, ll maior, ll type)
{
    if (minimo == menor && maximo == maior)
        return segment_tree[i][type];
    ll med = (minimo + maximo)/2;
    if (maior <= med)
        return intervalo (2*i+1, minimo, med, menor, maior, type);
    if (menor > med)
        return intervalo (2*i+2, med+1, maximo, menor, maior, type);
    if (type%2 == 0)
        return min (intervalo (2*i+1, minimo, med, menor, med, type), intervalo(2*i+2, med+1, maximo, med+1, maior, type));
}

ll minimo_r (ll a)
{
    return intervalo(0, 0, h*w-1, 0, a, 0);
}

ll maximo_r (ll a)
{
    return intervalo(0, 0, h*w-1, 0, a, 1);
}

ll minimo_c (ll a)
{
    return intervalo(0, 0, h*w-1, 0, a, 2);
}

ll maximo_c (ll a)
{
    return intervalo(0, 0, h*w-1, 0, a, 3);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
    r = R;
    c = C;
    h = H;
    w = W;
    create (0, 0, h*w-1);
    ll iterador = 0;
    while (iterador < h*w)
    {
        int maior_c = maximo_c(iterador);
        int menor_c = minimo_c(iterador);
        int maior_r = maximo_r(iterador);
        int menor_r = minimo_r (iterador);
        if ((maior_c - menor_c + 1)*(maior_r - menor_r + 1) == iterador + 1)
        {
            beautiful.insert (iterador);
            if (iterador == h*w-1)
                break;
            maior_c = max (maior_c, c[iterador+1]);
            menor_c = min (menor_c, c[iterador+1]);
            maior_r = max (maior_r, r[iterador+1]);
            menor_r = min (menor_r, r[iterador+1]);
        }
        iterador = (maior_c - menor_c + 1)*(maior_r - menor_r + 1) - 1;
    }
    return;
}

int swap_seats(int a, int b)
{
    if (a > b)
        swap (a, b);
    change(0, 0, h*w-1, a, r[b], 0);
    change(0, 0, h*w-1, a, r[b], 1);
    change(0, 0, h*w-1, a, c[b], 2);
    change(0, 0, h*w-1, a, c[b], 3);
    change(0, 0, h*w-1, b, r[a], 0);
    change(0, 0, h*w-1, b, r[a], 1);
    change(0, 0, h*w-1, b, c[a], 2);
    change(0, 0, h*w-1, b, c[a], 3);
    swap (r[a], r[b]);
    swap (c[a], c[b]);
    beautiful.erase (beautiful.lower_bound(a), beautiful.lower_bound(b));
    ll iterador = a;
    while (iterador <= b)
    {
        int maior_c = maximo_c(iterador);
        int menor_c = minimo_c(iterador);
        int maior_r = maximo_r(iterador);
        int menor_r = minimo_r (iterador);
        if ((maior_c - menor_c + 1)*(maior_r - menor_r + 1) == iterador + 1)
        {
            beautiful.insert (iterador);
            if (iterador == h*w-1)
                break;
            maior_c = max (maior_c, c[iterador+1]);
            menor_c = min (menor_c, c[iterador+1]);
            maior_r = max (maior_r, r[iterador+1]);
            menor_r = min (menor_r, r[iterador+1]);
        }
        iterador = (maior_c - menor_c + 1)*(maior_r - menor_r + 1) - 1;
    }
    return beautiful.size();
}

Compilation message (stderr)

seats.cpp: In function 'll intervalo(ll, ll, ll, ll, ll, ll)':
seats.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
   65 | }
      | ^

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