이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "seats.h"
#include <bits/stdc++.h>
#define INF (0x3f3f3f3f)
using namespace std;
const int MAXN = 1000055;
struct SEG {
int dp[MAXN*4][5], duc[MAXN*4], dbc[MAXN*4];
int n;
void init(int i, int s, int e) {
dp[i][0] = e-s+1;
if(s == e) return;
int m = (s+e) >> 1;
init(i<<1, s, m);
init(i<<1|1, m+1, e);
}
void init(int _n) {
n = _n;
init(1, 0, n-1);
}
void mv(int d[], int w) {
if(!w) return;
for(int i = 5; w < i--;) d[i] = d[i-w];
memset(d, 0, min(5, w)<<2);
}
void cal(int i, int s, int e) {
memset(dp[i], 0, 20);
if(dbc[i]) return;
if(s == e) dp[i][0] = 1;
else for(int j = 5; j--;) dp[i][j] = dp[i<<1][j] + dp[i<<1|1][j];
mv(dp[i], duc[i]);
}
void updb(int i, int s, int e, int p, int q, int x) {
if(q < p || e < p || q < s) return;
if(p <= s && e <= q) {
dbc[i] += x;
cal(i, s, e);
return;
}
int m = (s+e) >> 1;
updb(i<<1, s, m, p, q, x);
updb(i<<1|1, m+1, e, p, q, x);
cal(i, s, e);
}
void updu(int i, int s, int e, int p, int q, int x) {
if(q < p || e < p || q < s) return;
if(p <= s && e <= q) {
duc[i] += x;
if(0 <= x) mv(dp[i], x);
else cal(i, s, e);
return;
}
int m = (s+e) >> 1;
updu(i<<1, s, m, p, q, x);
updu(i<<1|1, m+1, e, p, q, x);
cal(i, s, e);
}
void updb(int s, int e, int x) { updb(1, 0, n-1, s, e, x); }
void updu(int s, int e, int x) { updu(1, 0, n-1, s, e, x); }
int get() { return dp[1][4]; }
} seg;
int A[MAXN], B[MAXN], **C;
int H, W, N;
void f(int y, int x, bool flag = false) {
int a[4] = { C[y][x], C[y][x+1], C[y+1][x], C[y+1][x+1] };
sort(a, a+4);
seg.updu(a[0], a[1]-1, flag ? -1 : 1);
seg.updb(a[2], a[3]-1, flag ? -1 : 1);
}
void g(int i, bool flag = false) {
int y = A[i], x = B[i];
for(int dy = 0; dy < 2; dy++) for(int dx = 0; dx < 2; dx++)
f(y-dy, x-dx, flag);
}
void give_initial_chart(int H, int W, std::vector<int> RV, std::vector<int> CV) {
::H = H; ::W = W; N = H*W;
C = new int*[H+2];
for(int i = H+2; i--;) {
C[i] = new int[W+2];
C[i][0] = C[i][W+1] = INF;
}
fill(C[0], C[0]+W+2, INF);
fill(C[H+1], C[H+1]+W+2, INF);
for(int i = N; i--;) {
A[i] = RV[i] + 1;
B[i] = CV[i] + 1;
C[A[i]][B[i]] = i;
}
seg.init(N);
for(int y = 0; y <= H; y++) for(int x = 0; x <= W; x++) f(y, x);
}
int swap_seats(int a, int b) {
g(a, true); g(b, true);
swap(C[A[a]][B[a]], C[A[b]][B[b]]);
swap(A[a], A[b]); swap(B[a], B[b]);
g(a); g(b);
return seg.get();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |