Submission #827492

#	Time	Username	Problem	Language	Result	Execution time	Memory
827492		I_Love_EliskaM_	Seats (IOI18_seats)	C++17	100 / 100	2618 ms	84960 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()
#define set(x,a,b,c,d) x[0]=a,x[1]=b,x[2]=c,x[3]=d;

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 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);
  
  if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
  else if (t[2*v+1].mn < t[2*v+2].mn) t[v]=t[2*v+1];
  else t[v]=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 add(int v, int l, int r, int lx, int rx, int x) {
  if (lazy[v]) {
    t[v].mn+=lazy[v];
    lazy[2*v+1]+=lazy[v];
    lazy[2*v+2]+=lazy[v];
    lazy[v]=0;
  }
  if (rx<=l || r<=lx) return;
  if (lx<=l && r<=rx) {
    t[v].mn+=x;
    lazy[2*v+1]+=x;
    lazy[2*v+2]+=x;
    return;
  }
  int m=(l+r)>>1;
  add(2*v+1,l,m,lx,rx,x);
  add(2*v+2,m,r,lx,rx,x);
  
  if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt};
  else if (t[2*v+1].mn < t[2*v+2].mn) t[v]=t[2*v+1];
  else t[v]=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;

int z[4];

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;
  
  for (int i=0; i<=n; ++i) {
    for (int j=0; j<=m; ++j) {
      set(z,a[i][j],a[i+1][j],a[i][j+1],a[i+1][j+1]);
      sort(z,z+4);
      add(z[0],z[1],1);
      add(z[2],z[3],1);
    }
  }
}

int swap_seats(int x, int y) {
  if (n==1 && m==1) return 1;
  
  int p=R[x], q=C[x], u=R[y], v=C[y];
 
  set(z,a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]);
  sort(z,z+4);
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);
 
  set(z,a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]);
  sort(z,z+4);
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);
 
  set(z,a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]);
  sort(z,z+4);
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);
 
  set(z,a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]);
  sort(z,z+4);
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);
 
 
  p=u, q=v;
 
  set(z,a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]);
  sort(z,z+4);
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);
 
  set(z,a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]);
  sort(z,z+4);
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);
 
  set(z,a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]);
  sort(z,z+4);
  add(z[0],z[1],-1);
  add(z[2],z[3],-1);
 
  set(z,a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]);
  sort(z,z+4);
  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];
 
  set(z,a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]);
  sort(z,z+4);
  add(z[0],z[1],1);
  add(z[2],z[3],1);
 
  set(z,a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]);
  sort(z,z+4);
  add(z[0],z[1],1);
  add(z[2],z[3],1);
 
  set(z,a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]);
  sort(z,z+4);
  add(z[0],z[1],1);
  add(z[2],z[3],1);
 
  set(z,a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]);
  sort(z,z+4);
  add(z[0],z[1],1);
  add(z[2],z[3],1);
 
 
  p=u, q=v;
 
  set(z,a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]);
  sort(z,z+4);
  add(z[0],z[1],1);
  add(z[2],z[3],1);
 
  set(z,a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]);
  sort(z,z+4);
  add(z[0],z[1],1);
  add(z[2],z[3],1);
 
  set(z,a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]);
  sort(z,z+4);
  add(z[0],z[1],1);
  add(z[2],z[3],1);
 
  set(z,a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]);
  sort(z,z+4);
  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