Submission #1326553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326553		SmuggingSpun	자리 배치 (IOI18_seats)	C++20	100 / 100	965 ms	99448 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void minimize(T& a, T b){
  if(a > b){
    a = b;
  }
}
template<class T>void maximize(T& a, T b){
  if(a < b){
    a = b;
  }
}
const int lim = 1e6 + 5;
int n, m, N, delta[lim], lazy[lim << 2];
pair<int, int>st[lim << 2];
vector<vector<int>>mat;
vector<int>r, c;
void build(int id, int l, int r){
  st[id] = make_pair(lazy[id] = 0, r - l + 1);
  if(l == r){
    return;
  }
  int m = (l + r) >> 1;
  build(id << 1, l, m);
  build(id << 1 | 1, m + 1, r);
}
void propagate(int id, int x){
  st[id].first += x;
  lazy[id] += x;
}
void push_down(int id){
  propagate(id << 1, lazy[id]);
  propagate(id << 1 | 1, lazy[id]);
  lazy[id] = 0;
}
pair<int, int>merge(pair<int, int>a, pair<int, int>b){
  if(a.first > b.first){
    swap(a, b);
  }
  else if(a.first == b.first){
    a.second += b.second;
  }
  return a;
}
void update(int id, int l, int r, int u, int v, int x){
  if(l > v || r < u){
    return;
  }
  if(u <= l && v >= r){
    propagate(id, x);
    return;
  }
  int m = (l + r) >> 1;
  push_down(id);
  update(id << 1, l, m, u, v, x);
  update(id << 1 | 1, m + 1, r, u, v, x);
  st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
int calc_delta(int i){
  if(i == 0){
    return 0;
  }
  int cnt_1 = 0, cnt_3 = 0;
  for(int ir = 0; ir < 2; ir++){
    for(int ic = 0; ic < 2; ic++){
      int cur = 0;
      for(int iir = 0; iir < 2; iir++){
        for(int iic = 0; iic < 2; iic++){
          int nr = r[i] - 1 + ir + iir, nc = c[i] - 1 + ic + iic;
          if(nr < 0 || nr >= n || nc < 0 || nc >= m || mat[nr][nc] > i){
            cur++;
          }
        }
      }
      if(cur == 1){
        cnt_1++;
      }
      else if(cur == 2){
        cnt_1--;
      }
      else if(cur == 3){
        cnt_3++;
      }
      else{
        cnt_3--;
      }
    }
  }
  return cnt_1 + cnt_3;
}
void update_delta(int x, int y){
  if(x < 0 || x >= n || y < 0 || y >= m || mat[x][y] == 0){
    return;
  }
  int i = mat[x][y], temp = delta[i];
  update(1, 0, N - 1, i, N - 1, (delta[i] = calc_delta(i)) - temp);
}
void give_initial_chart(int _H, int _W, vector<int>_R, vector<int>_C){
  swap(r, _R);
  swap(c, _C);
  build(1, 0, (N = (n = _H) * (m = _W)) - 1);
  mat.resize(n, vector<int>(m));
  for(int i = 0; i < N; i++){
    mat[r[i]][c[i]] = i;
  }
  memset(delta, 0, sizeof(delta));
  for(int i = 1; i < N; i++){
    update_delta(r[i], c[i]);
  }
}
int swap_seats(int a, int b){
  swap(r[a], r[b]);
  swap(c[a], c[b]);
  swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);
  for(int i = -1; i < 2; i++){
    for(int j = -1; j < 2; j++){
      update_delta(r[a] + i, c[a] + j);
      update_delta(r[b] + i, c[b] + j);
    }
  }
  return st[1].second;
}

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