Submission #292550

#	Time	Username	Problem	Language	Result	Execution time	Memory
292550		oolimry	Seats (IOI18_seats)	C++14	100 / 100	2588 ms	149488 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e9;
typedef pair<long long, int> ii;

///We want to see at each T, whether the numbers from 0 to T form a rectangle. We consider all squares from 0 to T labelled as black
///For some T, consider all 2x2 squares on the grid. A beautiful rectangle is formed if and only if:
///there are exactly 4 2x2 squares with 1 black square, and no 2x2 squares with 3 black squares.

///Let the 4 numbers in the 2x2 square be a, b, c, d where a < b < c < d.
///From T = a to T = b - 1, there is one more 2x2 square with one black square
///From T = c to T = d - 1, there is a 2x2 square with 3 black squares, hence it is impossible

///We can represent this as a segment tree for all T from 0 to HW - 1.
///For all T, the number of 2x2 squares with one black square cannot go below 4, hence it is sufficient to query if the minimum is 4, and if so, and how many 4s are there.
///We can do a range update(+1) from T = a to T = b - 1
///As for T = c to T = d - 1, we can add a very large number to indicate that we are "ruining" the range, as this range is completely impossible.

///Then for every swap, only 8 2x2 squares are affected.
///We can undo the range updates, swap the two values, and redo the range updates.


///we build a grid such that the boundaries are filled with the number n
int n, rows, cols;
static ii pos[1000005]; ///for each number, ii(r, c)
static vector<vector<int> > arr; ///arr[r*cols+c] is the element at (r,c)

///Everything here onwards is segment tree
///This is a range min range add segment tree, but we also store the no. of occurances of the minimum element
static ii tree[2000005]; ///we store the minimum element, and the number of occurances
static long long lazy[2000005]; 

///helper function to update the value of node i from the children of i
inline void relax(int i){
  if(tree[i<<1].first == tree[i<<1|1].first){
    tree[i] = ii(tree[i<<1].first+lazy[i], tree[i<<1].second + tree[i<<1|1].second);
  } 
  else{
    tree[i] = min(tree[i<<1],tree[i<<1|1]);
    tree[i].first += lazy[i];
  }
}

void initSegment(){
  for(int i = n;i < 2 * n;i++) tree[i] = ii(0,1);
  for(int i = n - 1;i >= 0;i--) relax(i);
}

inline void update(int l, int r, long long v){
  if(l == r) return;
  int ll = l + n, rr = r - 1 + n;
  for(l += n,r += n;l < r;l>>=1,r>>=1){
    if(l&1){
      tree[l].first += v;
      lazy[l] += v;
      l++;
    }
    if(r&1){
      r--;
      tree[r].first += v;
      lazy[r] += v;
    }
  }
  while(ll > 1){
    ll >>= 1;
    relax(ll);
  }
  while(rr > 1){
    rr >>= 1;
    relax(rr);
  }
}

///We need not propogate the lazy since we only query the entire range. We just store the lazy
inline int query(){
  return tree[1].second; ///the global minimum is definitely 4 (since 0 and everything form beautiful rectangles), hence just return the no. of occurances.
}

///consider a 2x2 square whose top-left corner is at r, c
void makeUpdate(int r, int c, bool isUndo){
  vector<int> values = {arr[r][c],arr[r+1][c],arr[r][c+1],arr[r+1][c+1]};
  sort(values.begin(),values.end());

  ///if isReverse, we undo our previous update
  if(isUndo){
    update(values[0],values[1],-1);
    update(values[2],values[3],-inf);
  }
  else{
    update(values[0],values[1],1); ///add one to the range, there is one more 2x2 square with exactly 1 black square
    update(values[2],values[3],inf); ///add infinity to "ruin" that range. When there are 2 black squares in the 2x2 square, it's impossible to have  beautiful rectangle
  }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  n = H * W;
  rows = H; cols = W;
  for(int i = 0;i < rows+2;i++){
    arr.push_back({});
    arr.back().assign(cols+2,n);
  }
  for(int i = 0;i < n;i++){
    R[i]++; C[i]++;
    arr[R[i]][C[i]] = i;
    pos[i] = ii(R[i],C[i]);
  }

  initSegment();

  for(int r = 0;r <= rows;r++){
    for(int c = 0;c <= cols;c++){
      makeUpdate(r,c,false);
    }
  }	
}

int swap_seats(int a, int b) {
  ii aPos = pos[a]; ii bPos = pos[b];

  ///undo updates for all affected rectangles
  makeUpdate(aPos.first-1,aPos.second-1,true);
  makeUpdate(aPos.first,aPos.second-1,true);
  makeUpdate(aPos.first-1,aPos.second,true);
  makeUpdate(aPos.first,aPos.second,true);
  makeUpdate(bPos.first-1,bPos.second-1,true);
  makeUpdate(bPos.first,bPos.second-1,true);
  makeUpdate(bPos.first-1,bPos.second,true);
  makeUpdate(bPos.first,bPos.second,true);


  ///swapping the elements
  pos[b] = aPos; pos[a] = bPos;
  arr[aPos.first][aPos.second] = b; arr[bPos.first][bPos.second] = a;


  ///now update again for all affected rectangles
  makeUpdate(aPos.first-1,aPos.second-1,false);
  makeUpdate(aPos.first,aPos.second-1,false);
  makeUpdate(aPos.first-1,aPos.second,false);
  makeUpdate(aPos.first,aPos.second,false);
  makeUpdate(bPos.first-1,bPos.second-1,false);
  makeUpdate(bPos.first,bPos.second-1,false);
  makeUpdate(bPos.first-1,bPos.second,false);
  makeUpdate(bPos.first,bPos.second,false);

  return query();
}

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