Submission #709815

#TimeUsernameProblemLanguageResultExecution timeMemory
709815CyanmondSeats (IOI18_seats)C++17
20 / 100
4041 ms237044 KiB
#include "seats.h" #include <bits/stdc++.h> template <class M> class SegmentTree { using T = typename M::T; int n, size; std::vector<T> data; void update(int i) { data[i] = M::op(data[2 * i], data[2 * i + 1]); } public: SegmentTree() {} SegmentTree(const std::vector<T> &vec) { n = (int)vec.size(); size = 1; while (size < n) { size *= 2; } data.assign(2 * size, M::e()); std::copy(vec.begin(), vec.end(), data.begin() + size); for (int i = size - 1; i >= 1; --i) update(i); } void set(int i, const T &v) { i += size; data[i] = v; while (i != 1) { i /= 2; update(i); } } T fold(int l, int r) { T pl = M::e(), pr = M::e(); for (l += size, r += size; l < r; l /= 2, r /= 2) { if (l & 1) pl = M::op(pl, data[l++]); if (r & 1) pr = M::op(data[--r], pr); } return M::op(pl, pr); } }; constexpr int inf = 1 << 30; struct MonoidMinMax { using T = std::pair<int, int>; static T op(const T &a, const T &b) { return {std::min(a.first, b.first), std::max(a.second, b.second)}; } static T e() { return {inf, -1}; } }; int H, W; std::vector<int> R, C; SegmentTree<MonoidMinMax> rowSeg, colSeg; std::vector<std::set<int>> rowIds, colIds; std::vector<std::pair<int, bool>> firstIds; void give_initial_chart(int h, int w, std::vector<int> r, std::vector<int> c) { H = h; W = w; R = r; C = c; if (H > W) { std::swap(H, W); std::swap(R, C); } std::vector<std::pair<int, int>> rInit(H * W), cInit(H * W); for (int i = 0; i < H * W; ++i) { rInit[i] = {R[i], R[i]}; cInit[i] = {C[i], C[i]}; } rowSeg = SegmentTree<MonoidMinMax>(rInit); colSeg = SegmentTree<MonoidMinMax>(cInit); rowIds.resize(H); colIds.resize(W); for (int i = 0; i < H * W; ++i) { if (colIds[C[i]].empty()) { firstIds.push_back({i, false}); } colIds[C[i]].insert(i); if (rowIds[R[i]].empty()) { firstIds.push_back({i, true}); } rowIds[R[i]].insert(i); } } void updRow(int i, int v, bool b) { int mi = *rowIds[i].begin(); auto itr = std::find(firstIds.begin(), firstIds.end(), std::make_pair(mi, true)); firstIds.erase(itr); if (b) rowIds[i].insert(v); else rowIds[i].erase(v); if (rowIds[i].empty()) return; mi = *rowIds[i].begin(); itr = std::lower_bound(firstIds.begin(), firstIds.end(), std::make_pair(mi, true)); firstIds.insert(itr, {mi, true}); } void updCol(int i, int v, bool b) { int mi = *colIds[i].begin(); auto itr = std::find(firstIds.begin(), firstIds.end(), std::make_pair(mi, false)); firstIds.erase(itr); if (b) colIds[i].insert(v); else colIds[i].erase(v); if (colIds[i].empty()) return; mi = *colIds[i].begin(); itr = std::lower_bound(firstIds.begin(), firstIds.end(), std::make_pair(mi, false)); firstIds.insert(itr, {mi, false}); } int swap_seats(int a, int b) { // upd updRow(R[a], a, false); updCol(C[a], a, false); updRow(R[b], b, false); updCol(C[b], b, false); updRow(R[a], b, true); updCol(C[a], b, true); updRow(R[b], a, true); updCol(C[b], a, true); rowSeg.set(a, std::make_pair(R[b], R[b])); rowSeg.set(b, std::make_pair(R[a], R[a])); colSeg.set(a, std::make_pair(C[b], C[b])); colSeg.set(b, std::make_pair(C[a], C[a])); std::swap(R[a], R[b]); std::swap(C[a], C[b]); // calc int answer = 0; int last = 0; for (const auto [i, b] : firstIds) { // at i - 1 if (last == i) { continue; } const auto x = rowSeg.fold(0, i), y = colSeg.fold(0, i); if ((x.second - x.first + 1) * (y.second - y.first + 1) == i) { ++answer; } last = i; } ++answer; return answer; }
#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...