Submission #991564

#	Time	Username	Problem	Language	Result	Execution time	Memory
991564		abczz	Seats (IOI18_seats)	C++14	33 / 100	1840 ms	149584 KiB

seats

#include "seats.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#define ll long long

using namespace std;

vector <vector <ll>> A;
ll n, m, dj[4][2] = {{-1, -1}, {-1, 0}, {0, -1}, {0, 0}};
array <ll, 2> X[1000000];
array <ll, 2> comp(array<ll, 2> x, array<ll, 2> y) {
  if (x[0] < y[0]) return x;
  else if (x[0] > y[0]) return y;
  else return {x[0], x[1]+y[1]};
}
array<ll, 2> get_mn(vector <ll> v) {
  sort(v.begin(), v.end());
  return {v[0], v[1]};
}

struct SegTree{
  struct Node{
    ll mnval = 0;
    ll mncnt = 0;
    ll lazy = 0;
  };
  vector <Node> st;
  void init() {
    st.resize(4*n*m);
    build(1, 0, n*m-1);
  }
  void build(ll id, ll l, ll r) {
    if (l == r) {
      st[id].mncnt = 1;
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    st[id].mncnt = r-l+1;
  }
  void push(ll id) {
    st[id*2].mnval += st[id].lazy, st[id*2].lazy += st[id].lazy;
    st[id*2+1].mnval += st[id].lazy, st[id*2+1].lazy += st[id].lazy;
    st[id].lazy = 0;
  }
  void update(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql) return;
    else if (ql <= l && r <= qr) {
      st[id].mnval += w, st[id].lazy += w;
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    update(id*2, l, mid, ql, qr, w);
    update(id*2+1, mid+1, r, ql, qr, w);
    array <ll, 2> tmp = comp({st[id*2].mnval, st[id*2].mncnt}, {st[id*2+1].mnval, st[id*2+1].mncnt});
    st[id] = {tmp[0], tmp[1], 0};
  }
  ll ans() {
    return st[1].mnval == 4 ? st[1].mncnt : 0;
  }
}ST;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  n = H, m = W;
  A.resize(n+2);
  ST.init();
  for (int i=0; i<=n+1; ++i) {
    A[i].resize(m+2);
    for (int j=0; j<=m+1; ++j) {
      A[i][j] = 1e18;
    }
  }
  for (int i=0; i<n*m; ++i) {
    X[i] = {R[i]+1, C[i]+1};
    A[R[i]+1][C[i]+1] = i;
  }
  for (int i=0; i<=n; ++i) {
    for (int j=0; j<=m; ++j) {
      auto [l, r] = get_mn({A[i][j], A[i+1][j], A[i][j+1], A[i+1][j+1]});
      ST.update(1, 0, n*m-1, l, n*m-1, 1);
      if (r != 1e18) ST.update(1, 0, n*m-1, r, n*m-1, -1);
    }
  }
}

void check(ll x, ll y, ll w) {
  for (int i=0; i<4; ++i) {
    auto xx = x + dj[i][0], yy = y + dj[i][1];
    auto [l, r] = get_mn({A[xx][yy], A[xx+1][yy], A[xx][yy+1], A[xx+1][yy+1]});
    ST.update(1, 0, n*m-1, l, n*m-1, w);
    if (r != 1e18) ST.update(1, 0, n*m-1, r, n*m-1, -w);
  }
}

int swap_seats(int a, int b) {
  check(X[a][0], X[a][1], -1);
  check(X[b][0], X[b][1], -1);
  swap(A[X[a][0]][X[a][1]], A[X[b][0]][X[b][1]]);
  swap(X[a], X[b]);
  check(X[a][0], X[a][1], 1);
  check(X[b][0], X[b][1], 1);
  return ST.ans();
}

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:82:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |       auto [l, r] = get_mn({A[i][j], A[i+1][j], A[i][j+1], A[i+1][j+1]});
      |            ^
seats.cpp: In function 'void check(long long int, long long int, long long int)':
seats.cpp:92:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |     auto [l, r] = get_mn({A[xx][yy], A[xx+1][yy], A[xx][yy+1], A[xx+1][yy+1]});
      |          ^

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