Submission #1248645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248645		countless	Seats (IOI18_seats)	C++20	5 / 100	4094 ms	39476 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

struct bit2d {
    int n, m;
    vector<vector<ll>> bit;

    bit2d(int n, int m) : n(n), m(m), bit(n+1, vector<ll>(m+1)) {;;}

    void add(int r, int c, ll val) {
        r++, c++;
        for (; r <= n; r += r & -r) {
            for (int i = c; i <= m; i += i & -i) {
                bit[r][i] += val;
            }
        }
    }

    ll sum(int r, int c) {
        r++, c++;
        ll res = 0;
        for (; r; r -= r & -r) {
            for (int i = c; i; i -= i & -i) {
                res += bit[r][i];
            }
        }
        return res;
    }

    ll sum(int r1, int c1, int r2, int c2) {
        return sum(r2, c2) - sum(r2, c1-1) - sum(r1-1, c2) + sum(r1-1, c1-1);
    }
};

ll h, w;
vector<ll> r, c;
bit2d *st;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    h = H, w = W;
    r = vector<ll>(R.begin(), R.end());
    c = vector<ll>(C.begin(), C.end());

    st = new bit2d(h, w);
    for (ll i = 0; i < h * w; i++) {
        st->add(r[i], c[i], i);
    }
}

inline ll mhash(ll r1, ll c1, ll r2, ll c2) {
    if (r2 < r1) swap(r1, r2);
    if (c2 < c1) swap(c1, c2);
    return r1 + (c1 * w) + (r2 * h * w) + (c2 * h * w * w);
}

bool check(int r1, int c1, int r2, int c2, map<ll, bool> &vis) {
    if (r2 < r1) swap(r1, r2);
    if (c2 < c1) swap(c1, c2);
    if (vis[mhash(r1, c1, r2, c2)]) return false;
    ll he = r2 - r1 + 1, we = c2 - c1 + 1;
    ll amt = he * we;
    ll tri = amt * (amt - 1) / 2;
    ll que = st->sum(r1, c1, r2, c2);

    // cerr << r1 sp c1 sp r2 sp c2 sp tri sp que << endl;
    vis[mhash(r1, c1, r2, c2)] = true;
    return tri == que;
}

// to opt: process in linear order (must always eq 0, etc)
int swap_seats(int a, int b) {
    // perform swap
    {
        if (a > b) swap(a, b);
        ll diff = b - a;

        st->add(r[a], c[a], diff);
        st->add(r[b], c[b], -diff);
        // cerr << st->sum(r[a], c[a], r[a], c[a]) << endl;

        swap(r[a], r[b]);
        swap(c[a], c[b]);
    }

    // count
    map<ll, bool> vis;
    int res = 0;
    ll r1, c1, r2, c2;
    r1 = r2 = r[0];
    c1 = c2 = c[0];
    // cerr << r1 sp c1 sp r2 sp c2 << endl;
    res += check(r1, c1, r2, c2, vis);
    for (ll i = 1; i < h * w; i++) {
        r1 = min(r1, r[i]);
        r2 = max(r2, r[i]);

        c1 = min(c1, c[i]);
        c2 = max(c2, c[i]);

        // cerr << r1 sp c1 sp r2 sp c2 sp check(r1, c1, r2, c2) << endl;
        res += check(r1, c1, r2, c2, vis);
    }

    return res;
}

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