Submission #600906

#	Time	Username	Problem	Language	Result	Execution time	Memory
600906		jack715	Seats (IOI18_seats)	C++14	25 / 100	4086 ms	121952 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second

using namespace std;

vector<int> row, col;
int val[1000][1000], hmax[1000][1000][10], wmax[1000][1000][10];
int h, w;

void calcwmax(int indx) {
  for (int i = 0; i < h-1; i++) 
    wmax[indx][i][0] = val[i+1][indx];
  
  for (int j = 1; j < 10; j++) {
    for (int i = 0; i < h; i++) {
      if (i + (1<<j) >= h) continue;
      wmax[indx][i][j] = max(wmax[indx][i][j-1], wmax[indx][i+(1<<(j-1))][j-1]);
    }
  }
}

void calchmax(int indx) {
  for (int i = 0; i < w-1; i++) 
    hmax[indx][i][0] = val[indx][i+1];
  
  for (int j = 1; j < 10; j++) {
    for (int i = 0; i < w; i++) {
      if (i + (1<<j) >= w) continue;
      hmax[indx][i][j] = max(hmax[indx][i][j-1], hmax[indx][i+(1<<(j-1))][j-1]);
    }
  }
}

int findwmax(int indx, int l, int r) {
  int ans = val[l][indx];
  for (int i = 9; i >= 0; i--) {
    if (l + (1 << i) > r) continue; 
    ans = max(ans, wmax[indx][l][i]);
    l = l + (1 << i);
  }
  return ans;
}


int findhmax(int indx, int l, int r) {
  int ans = val[indx][l];
  for (int i = 9; i >= 0; i--) {
    if (l + (1 << i) > r) continue; 
    ans = max(ans, hmax[indx][l][i]);
    l = l + (1 << i);
  }
  return ans;
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  row = R;
  col = C; 
  h = H;
  w = W; 
  for (int i = 0; i < h*w; i++)
    val[R[i]][C[i]] = i;
  for (int i = 0; i < h; i++)
    calchmax(i);
  for (int j = 0; j < w; j++)
    calcwmax(j);
}

int swap_seats(int A, int B) {
  swap(row[A], row[B]);
  swap(col[A], col[B]);
  val[row[A]][col[A]] = A;
  val[row[B]][col[B]] = B;
  calchmax(row[A]);
  calchmax(row[B]);
  calcwmax(col[A]);
  calcwmax(col[B]);

  int t = row[0], b = row[0], l = col[0], r = col[0], mx = 0, ans = 1;
  while (t > 0 || b < h-1 || l > 0 || r < w-1) {
    int now = h*w+5;
    if (t != 0) 
      now = min(now, findhmax(t-1, l, r));
    if (b != h-1)
      now = min(now, findhmax(b+1, l, r));
    if (l != 0) 
      now = min(now, findwmax(l-1, t, b));
    if (r != w-1)
      now = min(now, findwmax(r+1, t, b));
    
    if (t != 0 && findhmax(t-1, l, r) == now)
      t--;
    else if (b != h-1 && findhmax(b+1, l, r) == now)
      b++;
    else if (l != 0 && findwmax(l-1, t, b) == now) 
      l--;
    else if (r != w-1 && findwmax(r+1, t, b) == now)
      r++;
    
    // cout << l << ' ' << t << ' ' << r << ' ' << b << '\n';
    // cout << now << ' ' << mx << '\n';
    mx = max(mx, now);
    if ((r-l+1)*(b-t+1) == mx+1) ans++;
  }
  // cout << "=======\n";
  return ans;
}


/*
2 3 2
0 0
1 0
1 1 
0 1
0 2
1 2
0 5
0 5
*/

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