Submission #809562

#	Time	Username	Problem	Language	Result	Execution time	Memory
809562		becaido	Seats (IOI18_seats)	C++17	70 / 100	4018 ms	164496 KiB

seats

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "seats.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int SIZE = 1e6 + 5;

int n, m;
int x[SIZE], y[SIZE];
vector<int> a[SIZE];

/*
calculate how many times all 2x2 areas
there are exactly 4 1b3w and 0 3b1w
*/

pair<int, int> operator + (const pair<int, int> &l, const pair<int, int> &r) {
    return pair<int, int>(l.F + r.F, l.S + r.S);
}
pair<int, int>& operator += (pair<int, int> &l, const pair<int, int> &r) {
    return l = l + r;
}

struct Node {
    pair<int, int> mn, lazy;
    int cnt;
    Node() = default;
    Node operator + (const Node &r) const {
        Node re = Node();
        re.mn = min(mn, r.mn);
        re.cnt = (mn == re.mn ? cnt : 0) + (r.mn == re.mn ? r.cnt : 0);
        return re;
    }
} node[SIZE * 4];

void push(int pos, int l, int r) {
    node[pos].mn += node[pos].lazy;
    if (l < r) {
        node[lpos].lazy += node[pos].lazy;
        node[rpos].lazy += node[pos].lazy;
    }
    node[pos].lazy = {0, 0};
}
void pull(int pos, int l, int r) {
    int mid = (l + r) / 2;
    push(lpos, l, mid);
    push(rpos, mid + 1, r);
    node[pos] = node[lpos] + node[rpos];
}

void build(int pos, int l, int r) {
    if (l == r) {
        node[pos].cnt = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(lpos, l, mid);
    build(rpos, mid + 1, r);
    node[pos].cnt = node[lpos].cnt + node[rpos].cnt;
}
void upd(int pos, int l, int r, int L, int R, pair<int, int> x) {
    if (l == L && r == R) {
        node[pos].lazy += x;
        return;
    }
    push(pos, L, R);
    int mid = (L + R) / 2;
    if (r <= mid) upd(lpos, l, r, L, mid, x);
    else if (l > mid) upd(rpos, l, r, mid + 1, R, x);
    else {
        upd(lpos, l, mid, L, mid, x);
        upd(rpos, mid + 1, r, mid + 1, R, x);
    }
    pull(pos, L, R);
}
void upd(int l, int r, pair<int, int> x) {
    if (l > r) return;
    upd(1, l, r, 0, n * m - 1, x);
}
int que() {
    push(1, 0, n * m - 1);
    if (node[1].mn == make_pair(4, 0)) return node[1].cnt;
    return 0;
}

void add(int i, int j, int delta) {
    vector<int> t;
    FOR (di, 0, 1) FOR (dj, 0, 1) {
        if (min(i + di, j + dj) < 0 || i + di >= n || j + dj >= m) t.pb(n * m);
        else t.pb(a[i + di][j + dj]);
    }
    sort(t.begin(), t.end());
    upd(t[0], t[1] - 1, {delta, 0});
    upd(t[2], t[3] - 1, {0, delta});
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    n = H, m = W;
    FOR (i, 0, n - 1) a[i].resize(m);
    FOR (i, 0, n * m - 1) {
        tie(x[i], y[i]) = make_pair(R[i], C[i]);
        a[x[i]][y[i]] = i;
    }
    build(1, 0, n * m - 1);
    FOR (i, -1, n - 1) FOR (j, -1, m - 1) add(i, j, 1);
}

int swap_seats(int l, int r) {
    FOR (dx, -1, 0) FOR (dy, -1, 0) {
        add(x[l] + dx, y[l] + dy, -1);
        add(x[r] + dx, y[r] + dy, -1);
    }
    swap(a[x[l]][y[l]], a[x[r]][y[r]]);
    swap(x[l], x[r]), swap(y[l], y[r]);
    FOR (dx, -1, 0) FOR (dy, -1, 0) {
        add(x[l] + dx, y[l] + dy, 1);
        add(x[r] + dx, y[r] + dy, 1);
    }
    return que();
}

#ifdef WAIMAI
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int H = read_int();
  int W = read_int();
  int Q = read_int();
  vector<int> R(H * W), C(H * W);
  for (int i = 0; i < H * W; ++i) {
    R[i] = read_int();
    C[i] = read_int();
  }
  vector<int> A(Q), B(Q);
  for (int j = 0; j < Q; ++j) {
    A[j] = read_int();
    B[j] = read_int();
  }

  give_initial_chart(H, W, R, C);
  for (int j = 0; j < Q; ++j) {
    int answer = swap_seats(A[j], B[j]);
    printf("%d\n", answer);
  }
  return 0;
}
#endif

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