Submission #1023880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023880		Dzadzo	Seats (IOI18_seats)	C++17	100 / 100	2466 ms	188500 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vp vector<pii>
#define vvp vector<vp>
#define vb vector<bool>
#define vvb vector<vb>
#define INF INT_MAX
#define MOD 1000000007
#define MAXN 1000000
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

vp t(4 * MAXN + 1);
int lazy[4 * MAXN + 1];

pii merge(pii a, pii b) {
    if (a.F > b.F) return b;
    if (a.F < b.F) return a;
    return {a.F, a.S + b.S};
}

void build(int v, int tl, int tr) {
    if (tl == tr) t[v] = {0, 1};
    else {
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm);
        build(v * 2 + 1, tm + 1, tr);
        t[v] = merge(t[v * 2], t[v * 2 + 1]);
    }
}

void push(int v) {
    if (lazy[v] != 0) {
        t[v * 2].F += lazy[v];
        t[v * 2 + 1].F += lazy[v];
        lazy[v * 2] += lazy[v];
        lazy[v * 2 + 1] += lazy[v];
        lazy[v] = 0;
    }
}

void up(int v, int tl, int tr, int l, int r, int delta) {
    if (l > r) return;
    if (tl == l && tr == r) {
        t[v].F += delta;
        lazy[v] += delta;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        up(v * 2, tl, tm, l, min(r, tm), delta);
        up(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, delta);
        t[v] = merge(t[v * 2], t[v * 2 + 1]);
    }
}

vvi arr;
vvb seen;
int n, H, W;

void add(int x, int y, int t) {
    vi v = {arr[x][y], arr[x + 1][y], arr[x][y + 1], arr[x + 1][y + 1]};
    sort(v.begin(), v.end());
    up(1, 1, n, v[0], min(n, v[1] - 1), t);
    up(1, 1, n, v[2], min(n, v[3] - 1), t);
}

vi R, C;

void give_initial_chart(int h, int w, vi r, vi c) {
    R = r;
    C = c;
    H = h;
    W = w;
    n = H * W;
    build(1, 1, n);
    arr.resize(H + 2, vi(W + 2, 0));
    seen.resize(H + 2, vb(W + 2, false));

    for (int i = 0; i < n; i++) arr[R[i] + 1][C[i] + 1] = i + 1;
    for (int i = 0; i <= W + 1; i++) arr[0][i] = arr[H + 1][i] = INF;
    for (int i = 0; i <= H + 1; i++) arr[i][0] = arr[i][W + 1] = INF;

    for (int i = 0; i <= H; i++)
        for (int j = 0; j <= W; j++)
            add(i, j, 1);
}

int swap_seats(int a, int b) {
    vp cur = {
        {R[a] + 1, C[a] + 1}, {R[a], C[a] + 1}, {R[a] + 1, C[a]},
        {R[a], C[a]}, {R[b] + 1, C[b] + 1}, {R[b] + 1, C[b]},
        {R[b], C[b] + 1}, {R[b], C[b]}
    };

    for (auto &[x, y] : cur) {
        if (!seen[x][y]) add(x, y, -1);
        seen[x][y] = true;
    }

    for (auto &[x, y] : cur) seen[x][y] = false;

    swap(arr[R[a] + 1][C[a] + 1], arr[R[b] + 1][C[b] + 1]);
    swap(R[a], R[b]);
    swap(C[a], C[b]);

    for (auto &[x, y] : cur) {
        if (!seen[x][y]) add(x, y, 1);
        seen[x][y] = true;
    }

    for (auto &[x, y] : cur) seen[x][y] = false;

    return t[1].S;
}

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