Submission #1213072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213072		HappyCapybara	Seats (IOI18_seats)	C++17	100 / 100	2705 ms	125680 KiB

seats

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

int h, w;
vector<int> r, c;
vector<vector<int>> g;
vector<pair<int,int>> st;
vector<int> lazy;

void pushdown(int node, int tl, int tr){
  if (lazy[node] == 0) return;
  if (tl != tr){
    st[node*2].first += lazy[node];
    lazy[node*2] += lazy[node];
    st[node*2+1].first += lazy[node];
    lazy[node*2+1] += lazy[node];
  }
  lazy[node] = 0;
}

void update(int l, int r, int v, int node=1, int tl=0, int tr=h*w-1){
  pushdown(node, tl, tr);
  if (l > r) return;
  if (l <= tl && tr <= r){
    st[node].first += v;
    lazy[node] = v;
    return;
  }
  int tm = (tl+tr)/2;
  if (l <= tm) update(l, r, v, node*2, tl, tm);
  if (tm+1 <= r) update(l, r, v, node*2+1, tm+1, tr);
  if (st[node*2].first == st[node*2+1].first) st[node] = {st[node*2].first, st[node*2].second+st[node*2+1].second};
  else st[node] = min(st[node*2], st[node*2+1]);
}

vector<int> fb(int t, int l){
  vector<int> v = {g[t][l], g[t][l+1], g[t+1][l], g[t+1][l+1]};
  sort(v.begin(), v.end());
  return v;
}

void build(int node=1, int tl=0, int tr=h*w-1){
  st[node].second = (tr-tl)+1;
  if (tl == tr) return;
  int tm = (tl+tr)/2;
  build(node*2, tl, tm);
  build(node*2+1, tm+1, tr);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
  h = H;
  w = W;
  r = R;
  c = C;
  g.resize(h+2, vector<int>(w+2, h*w));
  for (int i=0; i<h*w; i++) g[r[i]+1][c[i]+1] = i;
  st.resize(4*h*w, {0, 1});
  build();
  lazy.resize(4*h*w, 0);
  for (int i=0; i<=h; i++){
    for (int j=0; j<=w; j++){
      vector<int> k = fb(i, j);
      update(k[0], h*w-1, 1);
      update(k[1], h*w-1, -1);
      update(k[2], h*w-1, 1);
      update(k[3], h*w-1, -1);
    }
  }
}

void cook(int a, int v){
  for (int t = r[a]; t <= r[a]+1; t++){
    for (int l = c[a]; l <= c[a]+1; l++){
      vector<int> k = fb(t, l);
      update(k[0], h*w-1, 1*v);
      update(k[1], h*w-1, -1*v);
      update(k[2], h*w-1, 1*v);
      update(k[3], h*w-1, -1*v);
    }
  }
}

int swap_seats(int a, int b){
  cook(a, -1);
  cook(b, -1);
  swap(g[r[a]+1][c[a]+1], g[r[b]+1][c[b]+1]);
  swap(r[a], r[b]);
  swap(c[a], c[b]);
  cook(a, 1);
  cook(b, 1);
  return st[1].second;
}

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