Submission #76580

#	Time	Username	Problem	Language	Result	Execution time	Memory
76580		Xylofo	Seats (IOI18_seats)	C++14	100 / 100	3210 ms	111440 KiB

seats

#pragma GCC target("avx,avx2,sse,sse2")
#pragma GCC optimize("Ofast")
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < b; ++i)

struct T {
  int mn;
  int cnt;
  static T mrg(T a, T b){
    int mn = min(a.mn, b.mn);
    int cnt = (a.mn == mn ? a.cnt : 0) + (b.mn == mn ? b.cnt : 0);
    return T{mn,cnt};
  }
  static T small() { return T{2123123, 0}; }
  static T def() { return T{0, 1}; }
};

#define cc(x) complex<int>(x.mn, x.cnt)
struct ST {
  int n;
  vector<T> v;
  vector<int> delta;
  void init(int m) {
    n = 1;
    while(n < m) n *= 2;
    v.resize(2*n, T::small());
    delta.resize(2*n, 0);
    rep(i,0,m) v[i+n] = T::def();
    for(int i = n-1; i; --i) v[i] = T::mrg(v[2*i], v[2*i+1]);
  }
  void push(int t){
    if(delta[t] != 0) {
      if(t < n) {
        delta[2*t+0] += delta[t];
        delta[2*t+1] += delta[t];
      }
      v[t].mn += delta[t];
      delta[t] = 0;
    }
  }
  const T& query() {
    push(1);
    return v[1];
  }
  const T& upd(int t, int L, int R, int l, int r, int d) {
    push(t);
    if(l <= L && R <= r) {
      delta[t] += d;
      push(t);
      return v[t];
    }
    if(r <= L || R <= l) return v[t];
    int M = (L+R)/2;
    return v[t] = T::mrg(upd(2*t, L, M, l, r, d), upd(2*t+1, M, R, l, r, d));
  }
  void update(int l, int r, int d){
    r = min(n,r);
    upd(1, 0, n, l, r, d);
  }
};

struct HW {
  int n;
  vector<int> r, c;
  ST st;
  int H, W;
  int cnt;
  bool ini;
  set<int> active;
  vector<vector<int> > board;
  void init(vector<int> r_, vector<int> c_, int H_, int W_){
    H = H_;
    W = W_;
    r = r_;
    c = c_;
    n = r.size();
    st.init(n);
    board.resize(H, vector<int>(W));
    rep(i,0,n) board[r[i]][c[i]] = i;
    rep(x,-1,H) rep(y,-1,W) sqr(x,y,1);
  }
  int gt(int a, int b){
    if(a < 0 || b < 0 || a >= H || b >= W) return 2123123;
    else return board[a][b];
  }
  void sqr(int x, int y, int delta) {
    vector<int> all{gt(x,y),gt(x+1,y),gt(x,y+1),gt(x+1,y+1)};
    sort(all.begin(),all.end());
    vector<pair<int,int> > inv;
    int kk = min(gt(x+1,y),gt(x,y+1));
    int k0 = gt(x+1,y+1);
    if(k0 < kk) st.update(k0, kk, delta);
    if(all[2] < n-1) st.update(all[2], all[3], delta);
  }
  void update(int x, int y, int nw) {
    for(int delta : {-1,1}) {
      sqr(x-1,y-1,delta);
      sqr(x,y-1,delta);
      sqr(x-1,y,delta);
      sqr(x,y,delta);
      board[x][y] = nw;
    }
  }
  int calc() {
    T t = st.query();
    return t.cnt;
  }
  int swap(int a, int b){
    if(a>b) std::swap(a,b);
    update(r[a], c[a], b);
    update(r[b], c[b], a);
    std::swap(r[a],r[b]);
    std::swap(c[a],c[b]);
    return calc();
  }
} hw;


void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  hw.init(R,C,H,W);
}

int swap_seats(int a, int b) {
  return hw.swap(a,b);
}

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