제출 #145263

#제출 시각아이디문제언어결과실행 시간메모리
145263kdh9949자리 배치 (IOI18_seats)C++17
37 / 100
4081 ms80760 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; const int N = 1000005; namespace S4{ int n, x[N], y[N], mx[N], Mx[N], my[N], My[N], r; void cal(int a[], int m[], int M[], int s, int e){ for(int i = s; i <= e; i++){ m[i] = min(m[i - 1], a[i]); M[i] = max(M[i - 1], a[i]); } } void ch(int s, int e, int x){ for(int i = s; i <= e; i++) if(1LL * (Mx[i] - mx[i] + 1) * (My[i] - my[i] + 1) == i) r += x; } void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { n = H * W; for(int i = 0; i < n; i++){ x[i + 1] = R[i]; y[i + 1] = C[i]; } mx[0] = my[0] = N; cal(x, mx, Mx, 1, n); cal(y, my, My, 1, n); ch(1, n, 1); } int swap_seats(int a, int b){ a++; b++; if(a > b) swap(a, b); swap(x[a], x[b]); swap(y[a], y[b]); ch(a, b - 1, -1); cal(x, mx, Mx, a, b - 1); cal(y, my, My, a, b - 1); ch(a, b - 1, 1); return r; } } namespace S3{ int n, x[N], y[N]; const int SZ = 1048576; struct Seg{ int m[2*SZ], M[2*SZ]; void i(){ fill(m, m + 2*SZ, N); fill(M, M + 2*SZ, -N); } void u(int x, int y){ x += SZ; m[x] = M[x] = y; for(x /= 2; x; x /= 2){ m[x] = min(m[2*x], m[2*x+1]); M[x] = max(M[2*x], M[2*x+1]); } } int f(int t, int k){ int x = 1; for(; x < SZ; ){ if(t == 0 && m[2*x] <= k) x = 2*x; else if(t == 1 && M[2*x] >= k) x = 2*x; else x = 2*x+1; } return x - SZ; } int ff(int s, int e){ return min(f(0, s - 1), f(1, e + 1)); } } X, Y; void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { n = H * W; X.i(); Y.i(); for(int i = 0; i < n; i++){ x[i + 1] = R[i]; y[i + 1] = C[i]; X.u(i + 1, R[i]); Y.u(i + 1, C[i]); } } int f(int sx, int ex, int sy, int ey){ int t = min(X.ff(sx, ex), Y.ff(sy, ey)); if(t > n) return 1; return (t == 1LL * (ex - sx + 1) * (ey - sy + 1) + 1) + f(min(sx, x[t]), max(ex, x[t]), min(sy, y[t]), max(ey, y[t])); } int swap_seats(int a, int b){ a++; b++; swap(x[a], x[b]); swap(y[a], y[b]); X.u(a, x[a]); X.u(b, x[b]); Y.u(a, y[a]); Y.u(b, y[b]); return f(x[1], x[1], y[1], y[1]); } } int ST; void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { ST = (H <= 1000 && W <= 1000 ? 3 : 4); if(ST == 3) S3::give_initial_chart(H, W, R, C); else S4::give_initial_chart(H, W, R, C); } int swap_seats(int a, int b){ if(ST == 3) return S3::swap_seats(a, b); return S4::swap_seats(a, b); }
#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...