Submission #1073136

#TimeUsernameProblemLanguageResultExecution timeMemory
1073136TobSeats (IOI18_seats)C++14
0 / 100
154 ms48176 KiB
#include <bits/stdc++.h> #include "seats.h" #define F first #define S second #define all(x) x.begin(), x.end() #define pb push_back #define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; typedef long long ll; typedef pair <ll, ll> pii; typedef array <int, 3> node; const int ofs = (1 << 3); int n, m; int r[ofs], c[ofs], mat[3*ofs], dx[4]; node t[2*ofs]; node Merge(node x, node y) { y[1] += x[0]; if (x[1] < y[1]) {x[0] += y[0]; return x;} if (x[1] > y[1]) {y[0] += x[0]; return y;} return {x[0]+y[0], x[1], x[2]+y[2]}; } void add(int x, int val) { if (x == ofs) return; x += ofs; t[x][0] += val; t[x][1] += val; t[x][2] = 1; while (x /= 2) t[x] = Merge(t[2*x], t[2*x+1]); } int get() {return t[1][2];} void give_initial_chart(int n_, int m_, vector<int> r_, vector<int> c_) { n = n_; m = m_; dx[0] = 1; dx[1] = m+2; dx[2] = -1; dx[3] = -m-2; for (int i = 0; i < n*m; i++) r[i] = r_[i]+1, c[i] = c_[i]+1; for (int i = 0; i <= n+1; i++) mat[i*(m+2)] = mat[i*(m+2)+m+1] = ofs; for (int i = 0; i <= m+1; i++) mat[i] = mat[(n+1)*(m+2)+i] = ofs; for (int i = 0; i < n*m; i++) mat[r[i]*(m+2)+c[i]] = i; for (int i = 1; i <= n+1; i++) { for (int j = 1; j <= m+1; j++) { int x = i*(m+2)+j; int b[4] = {mat[x-m-3], mat[x-m-2], mat[x-1], mat[x]}; sort(b, b+4); add(b[0], 1); add(b[1], -1); add(b[2], 1); add(b[3], -1); } } } void upd(int x, int o) { for (int i = 0; i < 4; i++) { int b[4] = {mat[x], mat[x+dx[i]], mat[x+dx[(i+1)&3]], mat[x+dx[i]+dx[(i+1)&3]]}; sort(b, b+4); add(b[0], o); add(b[1], -o); add(b[2], o); add(b[3], -o); } } int swap_seats(int a, int b) { int pa = r[a]*(m+2)+c[a], pb = r[b]*(m+2)+c[b]; upd(pa, -1); upd(pb, -1); swap(mat[pa], mat[pb]); swap(r[a], r[b]); swap(c[a], c[b]); upd(pa, 1); upd(pb, 1); return 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...