Submission #96820

#TimeUsernameProblemLanguageResultExecution timeMemory
96820youngyojunSeats (IOI18_seats)C++11
20 / 100
3580 ms220576 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...