Submission #434145

#	Time	Username	Problem	Language	Result	Execution time	Memory
434145		Tiago_Marques	Seats (IOI18_seats)	C++17	11 / 100	4098 ms	64580 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 minimo_r[1000000];
int maximo_r[1000000];
int minimo_c[1000000];
int maximo_c[1000000];
int ans = 1;
int segment_tree[4000000] = {};
bool beautiful[1000000] = {};

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

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

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
    r = R;
    c = C;
    h = H;
    w = W;
    minimo_r[0] = r[0];
    maximo_r[0] = r[0];
    minimo_c[0] = c[0];
    maximo_c[0] = c[0];
    change(0, 0, h*w-1, 0, 1);
    beautiful[0] = 1;
    REP(i, 1, H*W)
    {
        minimo_r[i] = min (minimo_r[i-1], r[i]);
        maximo_r[i] = max (maximo_r[i-1], r[i]);
        minimo_c[i] = min (minimo_c[i-1], c[i]);
        maximo_c[i] = max (maximo_c[i-1], c[i]);
        if ((maximo_r[i] - minimo_r[i] + 1)*(maximo_c[i] - minimo_c[i] + 1) == i+1)
        {
            ans ++;
            change (0, 0, h*w-1, i, 1);
            beautiful[i] = 1;
        }
    }
}

int swap_seats(int a, int b)
{
    if (a > b)
        swap (a, b);
    ans -= sum(0, 0, h*w-1, a, b);
    swap (r[a], r[b]);
    swap (c[a], c[b]);
    if (a == 0)
    {
        minimo_r[0] = r[0];
        maximo_r[0] = r[0];
        minimo_c[0] = c[0];
        maximo_c[0] = c[0];
        a++;
        ans ++;
    }
    REP(i, a, b+1)
    {
        minimo_r[i] = min (minimo_r[i-1], r[i]);
        maximo_r[i] = max (maximo_r[i-1], r[i]);
        minimo_c[i] = min (minimo_c[i-1], c[i]);
        maximo_c[i] = max (maximo_c[i-1], c[i]);
        if ((maximo_r[i] - minimo_r[i] + 1)*(maximo_c[i] - minimo_c[i] + 1) == i+1)
        {
            ans ++;
            if (!beautiful[i])
            {
                change (0, 0, h*w-1, i, 1);
                beautiful[i] = 1;
            }
        }
        else
        {
            if (beautiful[i])
            {
                change (0, 0, h*w-1, i, 0);
                beautiful[i] = 0;
            }
        }
    }
    return ans;
}

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