Submission #1012917

#TimeUsernameProblemLanguageResultExecution timeMemory
1012917c2zi6Seats (IOI18_seats)C++14
37 / 100
4043 ms80792 KiB
#define _USE_MATH_DEFINES #include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define all(a) (a).begin(), (a).end() #define replr(i, a, b) for (int i = int(a); i <= int(b); ++i) #define reprl(i, a, b) for (int i = int(a); i >= int(b); --i) #define rep(i, n) for (int i = 0; i < int(n); ++i) #define mkp(a, b) make_pair(a, b) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VPI; typedef vector<VI> VVI; typedef vector<VVI> VVVI; typedef vector<VPI> VVPI; typedef pair<ll, ll> PLL; typedef vector<ll> VL; typedef vector<PLL> VPL; typedef vector<VL> VVL; typedef vector<VVL> VVVL; typedef vector<VPL> VVPL; template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;} template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<class T> using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #include "seats.h" struct RECTANGLE { int mnx, mxx, mny, mxy; RECTANGLE() { mnx = mny = +2e9; mxx = mxy = -2e9; } void addcell(int x, int y) { setmin(mnx, x); setmax(mxx, x); setmin(mny, y); setmax(mxy, y); } int area() { if (mnx == +2e9) return -1; return (mxx-mnx+1) * (mxy-mny+1); } }; namespace TEST4 { int n, m; VPI tex; int ans; vector<RECTANGLE> pref; void give_initial_chart(int H, int W, VI R, VI C) { n = H; m = W; rep(i, n*m) tex.pb({R[i], C[i]}); pref = vector<RECTANGLE>(n*m+1); replr(i, 1, n*m) { pref[i] = pref[i-1]; auto[x, y] = tex[i-1]; pref[i].addcell(x, y); ans += (i == pref[i].area()); } } int swap_seats(int a, int b) { swap(tex[a], tex[b]); replr(i, min(a, b)+1, max(a, b)+1) { ans -= (i == pref[i].area()); pref[i] = pref[i-1]; auto[x, y] = tex[i-1]; pref[i].addcell(x, y); ans += (i == pref[i].area()); } return ans; } } /*SEGTREE*/ template<int DEFAULT, typename COMPORATOR> struct SEGTREE { int n; VI tree; COMPORATOR comp; int BEST(int a, int b) { if (comp(a, b)) return a; return b; } SEGTREE(){} SEGTREE(int sz) { n = 1; while (n < sz) n *= 2; tree = VI(2*n, DEFAULT); } void upd(int N, int L, int R, int i, int s) { if (i < L || i > R) return; if (L == R) { tree[N] = s; return; } int M = (L + R) / 2; upd(2*N+1, L, M, i, s); upd(2*N+2, M+1, R, i, s); tree[N] = BEST(tree[2*N+1], tree[2*N+2]); } int query(int N, int L, int R, int x) { if (!comp(tree[N], x)) return -1; if (L == R) return L; int M = (L + R) / 2; if (comp(tree[2*N+1], x)) return query(2*N+1, L, M, x); if (comp(tree[2*N+2], x)) return query(2*N+2, M+1, R, x); return -1; } void upd(int i, int s) { upd(0, 0, n-1, i, s); } int query(int x) { int ret = query(0, 0, n-1, x); if (ret == -1) return 2e9; return ret; } }; namespace TEST3 { int n, m; VPI tex; SEGTREE<(int)+2e9, less<int>> flx, fly; SEGTREE<(int)-2e9, greater<int>> fgx, fgy; void give_initial_chart(int H, int W, VI R, VI C) { n = H; m = W; rep(i, n*m) tex.pb({R[i], C[i]}); flx = fly = SEGTREE<(int)+2e9, less<int>>(n*m); fgx = fgy = SEGTREE<(int)-2e9, greater<int>>(n*m); rep(i, n*m) { auto[x, y] = tex[i]; flx.upd(i, x); fgx.upd(i, x); fly.upd(i, y); fgy.upd(i, y); } } int swap_seats(int a, int b) { swap(tex[a], tex[b]); for (int i : {a, b}) { auto[x, y] = tex[i]; flx.upd(i, x); fgx.upd(i, x); fly.upd(i, y); fgy.upd(i, y); } RECTANGLE cur; int curind = -1; int ans = 1; while (true) { int nextind = 2e9; setmin(nextind, flx.query(cur.mnx)); setmin(nextind, fgx.query(cur.mxx)); setmin(nextind, fly.query(cur.mny)); setmin(nextind, fgy.query(cur.mxy)); if (nextind == 2e9) break; int area = cur.area(); ans += (curind <= area-1 && area-1 < nextind); cur.addcell(tex[nextind].ff, tex[nextind].ss); curind = nextind; } return ans; } }; bool test3; void give_initial_chart(int H, int W, VI R, VI C) { if (H <= 1000 && W <= 1000) test3 = true; if (test3) TEST3::give_initial_chart(H, W, R, C); else TEST4::give_initial_chart(H, W, R, C); } int swap_seats(int a, int b) { if (test3) return TEST3::swap_seats(a, b); else return TEST4::swap_seats(a, b); }

Compilation message (stderr)

seats.cpp: In function 'void TEST4::give_initial_chart(int, int, VI, VI)':
seats.cpp:63:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |             auto[x, y] = tex[i-1];
      |                 ^
seats.cpp: In function 'int TEST4::swap_seats(int, int)':
seats.cpp:73:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |             auto[x, y] = tex[i-1];
      |                 ^
seats.cpp: In function 'void TEST3::give_initial_chart(int, int, VI, VI)':
seats.cpp:136:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  136 |             auto[x, y] = tex[i];
      |                 ^
seats.cpp: In function 'int TEST3::swap_seats(int, int)':
seats.cpp:146:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  146 |             auto[x, y] = tex[i];
      |                 ^
#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...