Submission #291699

#	Time	Username	Problem	Language	Result	Execution time	Memory
291699		SamAnd	Seats (IOI18_seats)	C++17	5 / 100	4065 ms	90372 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 1000006;

int n, m;
int x[N], y[N];

struct ban
{
    int minx, maxx;
    int miny, maxy;
    ban()
    {
        minx = miny = N;
        maxx = maxy = -1;
    }
    ban(int x, int y)
    {
        minx = maxx = x;
        miny = maxy = y;
    }
};

ban mer(const ban& l, const ban& r)
{
    ban res;
    res.minx = min(l.minx, r.minx);
    res.maxx = max(l.maxx, r.maxx);
    res.miny = min(l.miny, r.miny);
    res.maxy = max(l.maxy, r.maxy);
    return res;
}

ban t[N * 4];
void ubd(int tl, int tr, int x, pair<int, int> y, int pos)
{
    if (tl == tr)
    {
        t[pos] = ban(y.fi, y.se);
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, pos * 2);
    else
        ubd(m + 1, tr, x, y, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}

ban qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return ban();
    if (tl == l && tr == r)
    {
        return t[pos];
    }
    int m = (tl + tr) / 2;
    return mer(qry(tl, m, l, min(m, r), pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
    n = H;
    m = W;
    for (int i = 0; i < n * m; ++i)
    {
        x[i] = R[i];
        y[i] = C[i];
    }
    for (int i = 0; i < n * m; ++i)
        ubd(0, n * m - 1, i, m_p(x[i], y[i]), 1);
}

int swap_seats(int a, int b)
{
    swap(x[a], x[b]);
    swap(y[a], y[b]);
    ubd(0, n * m - 1, a, m_p(x[a], y[a]), 1);
    ubd(0, n * m - 1, b, m_p(x[b], y[b]), 1);
    int ans = 0;
    for (int i = 0; i < n * m; ++i)
    {
        ban u = qry(0, n * m - 1, 0, i, 1);
        if ((u.maxx - u.minx + 1) * (u.maxy - u.miny + 1) == i + 1)
            ++ans;
    }
    return ans;
}

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