Submission #827481

#	Time	Username	Problem	Language	Result	Execution time	Memory
827481		I_Love_EliskaM_	Seats (IOI18_seats)	C++17	100 / 100	2720 ms	83660 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 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);
}
inline 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);
  
  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 v[4];

void check(int i, int j, int x) {
  v[0] = a[i][j];
  v[1] = a[i][j+1];
  v[2] = a[i+1][j];
  v[3] = a[i+1][j+1];
  sort(v, v+4);
  add(v[0],v[1],x);
  add(v[2],v[3],x);
}

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) {
      check(i,j,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];
  vector<int> z;

  check(p,q,-1);
  check(p-1,q-1,-1);
  check(p-1,q,-1);
  check(p,q-1,-1);
  p=u, q=v;
  check(p,q,-1);
  check(p-1,q-1,-1);
  check(p-1,q,-1);
  check(p,q-1,-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];

  check(p,q,1);
  check(p-1,q-1,1);
  check(p-1,q,1);
  check(p,q-1,1);
  p=u, q=v;
  check(p,q,1);
  check(p-1,q-1,1);
  check(p-1,q,1);
  check(p,q-1,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