Submission #1225888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225888		mychecksedad	Seats (IOI18_seats)	C++17	100 / 100	635 ms	107544 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 4e6+100, M = 1e5+10, K = 52, MX = 30;


int nm, n, m, T[N][3], delta[N];
vector<array<int, 2>> pos;
vector<vi> grid;

void build(int l, int r, int k){
  if(l == r){
    T[k][0] = delta[l];
    T[k][1] = 1;
    T[k][2] = delta[l];
    return;
  }
  int mid = l+r>>1;
  build(l, mid, k<<1);
  build(mid+1, r, k<<1|1);
  if(T[k<<1][0] < T[k<<1|1][0] + T[k<<1][2]){
    T[k][0] = T[k<<1][0];
    T[k][1] = T[k<<1][1];
  }else if(T[k<<1|1][0] + T[k<<1][2] < T[k<<1][0]){
    T[k][0] = T[k<<1|1][0] + T[k<<1][2];
    T[k][1] = T[k<<1|1][1];
  }else{
    T[k][0] = T[k<<1][0];
    T[k][1] = T[k<<1][1] + T[k<<1|1][1];
  }
  T[k][2] = T[k<<1][2] + T[k<<1|1][2];
}

void upd(int l, int r, int p, int k){
  if(l == r){
    T[k][0] = delta[l];
    T[k][1] = 1;
    T[k][2] = delta[l];
    return;
  }
  int mid = l+r>>1;
  if(p <= mid) upd(l, mid, p, k<<1);
  else upd(mid + 1, r, p, k<<1|1);
  if(T[k<<1][0] < T[k<<1|1][0] + T[k<<1][2]){
    T[k][0] = T[k<<1][0];
    T[k][1] = T[k<<1][1];
  }else if(T[k<<1|1][0] + T[k<<1][2] < T[k<<1][0]){
    T[k][0] = T[k<<1|1][0] + T[k<<1][2];
    T[k][1] = T[k<<1|1][1];
  }else{
    T[k][0] = T[k<<1][0];
    T[k][1] = T[k<<1][1] + T[k<<1|1][1];
  }
  T[k][2] = T[k<<1][2] + T[k<<1|1][2];
}


int get(int x, int y, int k){
  if(x < 0 || y < 0 || x >= n || y >= m) return 0;
  return grid[x][y] <= k ? 1 : 0;
}

int get_delta(int x, int y, int k){
  int score = 0;
  for(int i = x - 1; i <= x; ++i){
    for(int j = y - 1; j <= y; ++j){
      int cnt = get(i, j, k - 1) + get(i + 1, j, k - 1) + get(i, j + 1, k - 1) + get(i + 1, j + 1, k - 1);
      int cnt2 = get(i, j, k) + get(i + 1, j, k) + get(i, j + 1, k) + get(i + 1, j + 1, k);
      score += (cnt2 == 1) + (cnt2 == 3) - (cnt == 1) - (cnt == 3); // delta
    }
  }
  return score;
}

void give_initial_chart(int nn, int mm, std::vector<int> R, std::vector<int> C) {
  n = nn;
  m = mm;
  nm = n * m;
  pos.resize(nm);
  grid.resize(n, vi(m));
  for(int i = 0; i < nm; ++i){
    pos[i] = {R[i], C[i]};
    grid[R[i]][C[i]] = i;
  }
  for(int i =0 ; i < nm; ++i){
    delta[i] = get_delta(R[i], C[i], i);
    // cerr << delta[i] << ' ';
  }
  build(0, nm-1, 1);
}

int swap_seats(int a, int b) {
  swap(pos[a], pos[b]);
  swap(grid[pos[a][0]][pos[a][1]], grid[pos[b][0]][pos[b][1]]);

  for(int rep = 0; rep < 2; ++rep){
    for(int i = pos[a][0] - 1; i <= pos[a][0] + 1; ++i){
      for(int j = pos[a][1] - 1; j <= pos[a][1] + 1; ++j){
        if(i < 0 || j < 0 || i >= n || j >= m) continue;
        delta[grid[i][j]] = get_delta(i, j, grid[i][j]);
        upd(0, nm-1, grid[i][j], 1);
      }
    }
    swap(a, b);
  }
  // cerr << "upd\n";

  // for(int i =0 ; i < nm; ++i){
  //   cerr << delta[i] << ' ';
  // }

  // delta[a] = get_delta(pos[a][0], pos[a][1], a);
  // delta[b] = get_delta(pos[b][0], pos[b][1], b);

  // upd(0, nm-1, a, 1);
  // upd(0, nm-1, b, 1);

  return (T[1][0] == 4 ? T[1][1] : 0);
}

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