Submission #700919

#	Time	Username	Problem	Language	Result	Execution time	Memory
700919		mychecksedad	Seats (IOI18_seats)	C++17	17 / 100	4074 ms	127636 KiB

seats

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;

int n, m, t[N*4][4], id[4] = {N, 0, N, 0}, A = 0;
vector<vector<int>> grid;
vector<array<int, 2>> pos;
vector<bool> is;

void build(int l, int r, int k){
  if(l == r){
    t[k][0] = pos[l - 1][0];
    t[k][1] = pos[l - 1][0];
    t[k][2] = pos[l - 1][1];
    t[k][3] = pos[l - 1][1];
    return;
  }
  int mid = l+r>>1;
  build(l, mid, k<<1);
  build(mid+1, r, k<<1|1);
  t[k][0] = min(t[k<<1][0], t[k<<1|1][0]);
  t[k][1] = max(t[k<<1][1], t[k<<1|1][1]);
  t[k][2] = min(t[k<<1][2], t[k<<1|1][2]);
  t[k][3] = max(t[k<<1][3], t[k<<1|1][3]);
}

void update(int l, int r, int p, int k){
  if(l == r){
    t[k][0] = pos[p - 1][0];
    t[k][1] = pos[p - 1][0];
    t[k][2] = pos[p - 1][1];
    t[k][3] = pos[p - 1][1];
    return;
  }
  int mid = l+r>>1;
  
  if(mid >= p)
    update(l, mid, p, k<<1);
  else
    update(mid + 1, r, p, k<<1|1);

  t[k][0] = min(t[k<<1][0], t[k<<1|1][0]);
  t[k][1] = max(t[k<<1][1], t[k<<1|1][1]);
  t[k][2] = min(t[k<<1][2], t[k<<1|1][2]);
  t[k][3] = max(t[k<<1][3], t[k<<1|1][3]);
}

int get(int l, int r, int ql, int qr, int k, int s){
  if(ql > r || qr < l) return id[s];
  if(ql <= l && r <= qr) return t[k][s];
  int mid = l+r>>1;
  int al = get(l, mid, ql, qr, k<<1, s);
  int ar = get(mid + 1, r, ql, qr, k<<1|1, s);
  return (s % 2 ? max(al, ar) : min(al, ar));
}

int calc(){
  int ans = 0;
  int u = n, d = 0, l = m, r = 0;
  for(int i = 0; i < n*m; ++i){
    u = min(u, pos[i][0]);
    d = max(d, pos[i][0]);
    l = min(l, pos[i][1]);
    r = max(r, pos[i][1]);
    if((r - l + 1) * (d - u + 1) == i + 1){
      ans++;
      is[i] = 1;
    }
  }
  return ans;
}
void calc2(int a, int b){
  int u = get(1, n*m, 1, a, 1, 0);
  int d = get(1, n*m, 1, a, 1, 1);
  int l = get(1, n*m, 1, a, 1, 2);
  int r = get(1, n*m, 1, a, 1, 3);
 
  for(int i = a - 1; i <= b - 1; ++i){
    u = min(u, pos[i][0]);
    d = max(d, pos[i][0]);
    l = min(l, pos[i][1]);
    r = max(r, pos[i][1]);
    if((r - l + 1) * (d - u + 1) == i + 1){
      if(!is[i]) A++;
      is[i] = 1;
    }else{
      if(is[i]) A--;
      is[i] = 0;
    }
  }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
  n = H, m = W;
  grid.resize(n, vector<int> (m, 0));
  is.resize(n*m);
  pos.resize(n*m);
  for(int i = 0; i < n*m; ++i) grid[R[i]][C[i]] = i, pos[i] = {R[i], C[i]};
  build(1, n*m, 1);
  A = calc();
}
int swap_seats(int a, int b){
  if(a > b) swap(a, b);
  if(b-a <= 10000){
    swap(pos[a], pos[b]);
    update(1, n*m, a + 1, 1);
    update(1, n*m, b + 1, 1);
    calc2(a + 1, b + 1);
    return A;
  }
  swap(pos[a], pos[b]);
  grid[pos[a][0]][pos[a][1]] = a;
  grid[pos[b][0]][pos[b][1]] = b;
  return calc();
}

Compilation message (stderr)

seats.cpp: In function 'void build(int, int, int)':
seats.cpp:18:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |   int mid = l+r>>1;
      |             ~^~
seats.cpp: In function 'void update(int, int, int, int)':
seats.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int mid = l+r>>1;
      |             ~^~
seats.cpp: In function 'int get(int, int, int, int, int, int)':
seats.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |   int mid = l+r>>1;
      |             ~^~

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