제출 #294181

#제출 시각아이디문제언어결과실행 시간메모리
294181Kastanda자리 배치 (IOI18_seats)C++11
33 / 100
2191 ms62200 KiB
// M #include<bits/stdc++.h> #include "seats.h" #define pb push_back #define lc (id << 1) #define rc (lc ^ 1) #define md ((l + r) >> 1) using namespace std; const int MXN = 1e6 + 10, N = 1009; int n, m, R[MXN], C[MXN], B[MXN]; int MN[MXN * 4], LZ[MXN * 4], Cnt[MXN * 4]; vector < vector < int > > A; void Build(int id = 1, int l = 0, int r = m) { Cnt[id] = r - l; if (r - l < 2) return ; Build(lc, l, md); Build(rc, md, r); } inline void Shift(int id) { MN[lc] += LZ[id]; MN[rc] += LZ[id]; LZ[lc] += LZ[id]; LZ[rc] += LZ[id]; LZ[id] = 0; } void Add(int le, int ri, int val, int id = 1, int l = 0, int r = m) { if (ri <= l || r <= le) return ; if (le <= l && r <= ri) { MN[id] += val; LZ[id] += val; return ; } Shift(id); Add(le, ri, val, lc, l, md); Add(le, ri, val, rc, md, r); MN[id] = min(MN[lc], MN[rc]); Cnt[id] = 0; if (MN[id] == MN[lc]) Cnt[id] += Cnt[lc]; if (MN[id] == MN[rc]) Cnt[id] += Cnt[rc]; } inline void Do(int i, int val) { //printf("%d : %d ::: %d\n", min(B[i], B[i + 1]), max(B[i], B[i + 1]), val); Add(min(B[i], B[i + 1]), max(B[i], B[i + 1]), val); } void give_initial_chart(int _H, int _W, vector < int > _R, vector < int > _C) { n = _H; m = _W; for (int i = 0; i < n * m; i ++) R[i] = _R[i], C[i] = _C[i]; for (int i = 0; i < n; i ++) A.pb(vector < int > (m, 0)); for (int i = 0; i < n * m; i ++) A[R[i]][C[i]] = i; assert(n == 1); for (int i = 0; i < m; i ++) B[C[i] + 1] = i; Build(); B[0] = B[m + 1] = m + 1; for (int i = 0; i <= m; i ++) Do(i, 1); } int swap_seats(int a, int b) { swap(R[a], R[b]); swap(C[a], C[b]); int c = C[a] + 1; int d = C[b] + 1; if (c > d) swap(c, d); Do(c - 1, -1); Do(c, -1); if (d - 1 > c) Do(d - 1, -1); Do(d, -1); swap(B[c], B[d]); Do(c - 1, 1); Do(c, 1); if (d - 1 > c) Do(d - 1, 1); Do(d, 1); return Cnt[1]; }
#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...