Submission #827448

#	Time	Username	Problem	Language	Result	Execution time	Memory
827448		I_Love_EliskaM_	Seats (IOI18_seats)	C++17	100 / 100	2790 ms	100264 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()

const int inf = 1e9;

const int sz = 1<<20;
struct node {
  int mn=inf, cnt=0;
  node(int a, int b) {mn=a,cnt=b;}
  node() {}
};
node merge(node a, node b) {
  if (a.mn==b.mn) return {a.mn, a.cnt+b.cnt};
  if (a.mn < b.mn) return a;
  return b;
}

node t[2*sz];
int lazy[4*sz];

void build(int v, int l, int r) {
  if (r-l==1) return;
  int m=(l+r)>>1;
  build(2*v+1,l,m);
  build(2*v+2,m,r);
  t[v]=merge(t[2*v+1],t[2*v+2]);
}
void init(int n, int m) {
  forn(i,n*m) t[sz-1+i]={0,1};
  build(0,0,sz);
}
void push(int v) {
  t[v].mn+=lazy[v];
  lazy[2*v+1]+=lazy[v];
  lazy[2*v+2]+=lazy[v];
  lazy[v]=0;
}
void add(int v, int l, int r, int lx, int rx, int x) {
  if (lazy[v]) push(v);
  if (rx<=l || r<=lx) return;
  if (lx<=l && r<=rx) {
    lazy[v]+=x;
    push(v);
    return;
  }
  int m=(l+r)>>1;
  add(2*v+1,l,m,lx,rx,x);
  add(2*v+2,m,r,lx,rx,x);
  t[v]=merge(t[2*v+1],t[2*v+2]);
}
void add(int l, int r, int x) {
  if (l>=r) return;
  add(0,0,sz,l,r,x);
}

int R[sz], C[sz];
int swapped=0;
int n,m;

vector<vector<int>> a;

void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) {
  n=_n, m=_m;
  if (n==1 && m==1) return;
  forn(i,n*m) R[i]=_r[i]+1, C[i]=_c[i]+1;
  if (m==1) {
    swap(n,m);
    forn(i,n*m) swap(R[i],C[i]);
    swapped=1;
  }
  init(n,m);

  a.assign(n+2,vector<int>(m+2,n*m));
  forn(i,n*m) a[R[i]][C[i]]=i;
  if (n==1) {
    forn(i,m+1) {
      int l=min(a[1][i],a[1][i+1]);
      int r=max(a[1][i],a[1][i+1]);
      add(l,r,1);
    }
  } else {
    for (int i=0; i<=n; ++i) {
      for (int j=0; j<=m; ++j) {
        vector<int> v = {a[i][j],a[i+1][j],a[i][j+1],a[i+1][j+1]};
        sort(all(v));
        add(v[0],v[1],1);
        add(v[2],v[3],1);
      }
    }
  }
}

int swap_seats(int x, int y) {
  if (n==1 && m==1) return 1;
  if (n==1) {
    assert(R[x]==1 && R[y]==1);

    int i=C[x], j=C[y];
    int l,r;

    l=min(a[1][i-1],a[1][i]);
    r=max(a[1][i-1],a[1][i]);
    add(l,r,-1);
    l=min(a[1][i+1],a[1][i]);
    r=max(a[1][i+1],a[1][i]);
    add(l,r,-1);
    l=min(a[1][j-1],a[1][j]);
    r=max(a[1][j-1],a[1][j]);
    add(l,r,-1);
    l=min(a[1][j+1],a[1][j]);
    r=max(a[1][j+1],a[1][j]);
    add(l,r,-1);

    swap(C[x],C[y]);
    swap(R[x],R[y]);
    a[R[x]][C[x]]=x;
    a[R[y]][C[y]]=y;
    i=C[x], j=C[y];

    l=min(a[1][i-1],a[1][i]);
    r=max(a[1][i-1],a[1][i]);
    add(l,r,1);
    l=min(a[1][i+1],a[1][i]);
    r=max(a[1][i+1],a[1][i]);
    add(l,r,1);
    l=min(a[1][j-1],a[1][j]);
    r=max(a[1][j-1],a[1][j]);
    add(l,r,1);
    l=min(a[1][j+1],a[1][j]);
    r=max(a[1][j+1],a[1][j]);
    add(l,r,1);
    return t[0].cnt;
  }
  
  int p=R[x], q=C[x], u=R[y], v=C[y];
  vector<int> z;

  z = {a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]};
  sort(all(z));
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);

  z = {a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]};
  sort(all(z));
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);

  z = {a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]};
  sort(all(z));
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);

  z = {a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]};
  sort(all(z));
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);


  p=u, q=v;

  z = {a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]};
  sort(all(z));
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);

  z = {a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]};
  sort(all(z));
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);

  z = {a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]};
  sort(all(z));
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);

  z = {a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]};
  sort(all(z));
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);


  swap(R[x],R[y]);
  swap(C[x],C[y]);
  a[R[x]][C[x]]=x;
  a[R[y]][C[y]]=y;


  p=R[x], q=C[x], u=R[y], v=C[y];

  z = {a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]};
  sort(all(z));
  add(z[0],z[1],1);
  add(z[2],z[3],1);

  z = {a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]};
  sort(all(z));
  add(z[0],z[1],1);
  add(z[2],z[3],1);

  z = {a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]};
  sort(all(z));
  add(z[0],z[1],1);
  add(z[2],z[3],1);

  z = {a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]};
  sort(all(z));
  add(z[0],z[1],1);
  add(z[2],z[3],1);


  p=u, q=v;

  z = {a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]};
  sort(all(z));
  add(z[0],z[1],1);
  add(z[2],z[3],1);

  z = {a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]};
  sort(all(z));
  add(z[0],z[1],1);
  add(z[2],z[3],1);

  z = {a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]};
  sort(all(z));
  add(z[0],z[1],1);
  add(z[2],z[3],1);

  z = {a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]};
  sort(all(z));
  add(z[0],z[1],1);
  add(z[2],z[3],1);

  return t[0].cnt;

}

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