Submission #277093

#TimeUsernameProblemLanguageResultExecution timeMemory
277093hamerinSeats (IOI18_seats)C++17
0 / 100
395 ms37368 KiB
#include "seats.h" #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; using i64 = long long; using d64 = long double; using pi = pair<int, int>; using pli = pair<i64, i64>; using ti = tuple<int, int, int>; using tli = tuple<i64, i64, i64>; #define iterall(cont) cont.begin(), cont.end() #define prec(n) setprecision(n) << fixed const i64 PINF = numeric_limits<i64>::max(); const i64 NINF = numeric_limits<i64>::min(); class segTree { public: vector<i64> vl; int N; segTree() = default; segTree(int _N) { vl.resize(1 << 21, NINF); N = _N; } void update(int s, int e, int n, int t, i64 ne) { if (s == e) { vl[n] = ne; return; } int m = (s + e) >> 1; int k = n << 1; if (t <= m) update(s, m, k, t, ne); else update(m + 1, e, k + 1, t, ne); vl[n] = max(vl[k], vl[k + 1]); } void update(int t, i64 ne) { update(1, N, 1, t, ne); } i64 query(int s, int e, int n, int l, int r) { if (r < s || e < l) return NINF; if (l <= s && e <= r) return vl[n]; int m = (s + e) >> 1; int k = n << 1; return max(query(s, m, k, l, r), query(m + 1, e, k + 1, l, r)); } i64 query(int l, int r) { return query(1, N, 1, l, r); } }; segTree sT; vector<int> c; void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { c = C; sT = segTree(W + 1); for (int i = 0; i < W; i++) sT.update(c[i] + 1, i); } int swap_seats(int a, int b) { swap(c[a], c[b]); sT.update(c[a] + 1, a); sT.update(c[b] + 1, b); int s = 0, e = c.size() - c[0] - 1; while (s < e) { int m = (s + e + 1) >> 1; if (sT.query(c[0] + 1, c[0] + m + 1) == m) s = m; else e = m - 1; } return s; }
#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...