제출 #110923

#제출 시각아이디문제언어결과실행 시간메모리
110923Just_Solve_The_Problem자리 배치 (IOI18_seats)C++11
5 / 100
4094 ms93176 KiB
#include "seats.h" //#include "grader.cpp" #define pii pair < int, int > #define fr first #define sc second #define mk make_pair #define OK puts("ok"); #define ll long long using namespace std; const int N = (int)1e6 + 7; const int inf = (int)1e9 + 7; int n; inline int min(const int &a, const int &b) { return (a < b) ? a : b; } inline int max(const int &a, const int &b) { return (a < b) ? b : a; } void swap(int &a, int &b) { int temp = a; a = b; b = temp; } struct T { int treemn[2 * N]; int treemx[2 * N]; T () { } void build(int v, int l, int r, vector <int> &V) { if (l == r) { treemn[v] = treemx[v] = V[l - 1]; return ; } int mid = (l + r) >> 1; build(v + v, l, mid, V); build(v + v + 1, mid + 1, r, V); treemn[v] = min(treemn[v + v], treemn[v + v + 1]); treemx[v] = max(treemx[v + v], treemx[v + v + 1]); } void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) { if (tl == tr) { treemn[v] = treemx[v] = val; return ; } int mid = (tl + tr) >> 1; if (pos <= mid) { upd(pos, val, v + v, tl, mid); } else { upd(pos, val, v + v + 1, mid + 1, tr); } treemn[v] = min(treemn[v + v], treemn[v + v + 1]); treemx[v] = max(treemx[v + v], treemx[v + v + 1]); } int getmin(int l, int r, int v = 1, int tl = 1, int tr = n) { if (tl > r || tr < l) return inf; if (l <= tl && tr <= r) return treemn[v]; int mid = (tl + tr) >> 1; return min(getmin(l, r, v + v, tl, mid), getmin(l, r, v + v + 1, mid + 1, tr)); } int getmax(int l, int r, int v = 1, int tl = 1, int tr = n) { if (tl > r || tr < l) return 0; if (l <= tl && tr <= r) return treemx[v]; int mid = (tl + tr) >> 1; return max(getmax(l, r, v + v, tl, mid), getmax(l, r, v + v + 1, mid + 1, tr)); } }; T tr[2]; int h, w; int ans; int r[N], c[N]; void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { h = H; w = W; n = h * w; tr[0].build(1, 1, n, R); tr[1].build(1, 1, n, C); for (int i = 0; i < n; i++) { c[i + 1] = C[i]; r[i + 1] = R[i]; } } int swap_seats(int a, int b) { a++; b++; swap(r[a], r[b]); swap(c[a], c[b]); tr[0].upd(a, r[a]); tr[1].upd(a, c[a]); tr[0].upd(b, r[b]); tr[1].upd(b, c[b]); ans = 0; ll area; for (ll i = 1; i <= n; ) { pair < int, int > tp1, tp2; tp1 = {tr[0].getmin(1, i), tr[0].getmax(1, i)}; tp2 = {tr[1].getmin(1, i), tr[1].getmax(1, i)}; area = (tp1.sc - tp1.fr + 1) * 1LL * (tp2.sc - tp2.fr + 1); if (i == area) { ans++; i++; } else { i = area; } } // cerr << ans << endl; return ans; }
#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...