제출 #274899

#제출 시각아이디문제언어결과실행 시간메모리
274899Haunted_Cpp자리 배치 (IOI18_seats)C++17
5 / 100
4056 ms90360 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 1e6 + 5; class SegmentTree { private: struct Node { int mn, mx; Node () { mx = -1e9; mn = 1e9; } void merge(Node esq, Node dir) { mn = min(esq.mn, dir.mn); mx = max(esq.mx, dir.mx); } }; int LO, HI; vector<Node> seg; void build(int l, int r, int node, const vector<int> &arr) { if (l == r) { seg[node].mn = seg[node].mx = arr[l]; return; } const int mid = l + (r - l) / 2; build(l, mid, 2 * node + 1, arr); build(mid + 1, r, 2 * node + 2, arr); seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]); } void modify(int l, int r, int where, int delta, int node) { if (l > where || r < where) return; if (l >= where && r <= where) { seg[node].mn = seg[node].mx = delta; return; } const int mid = l + (r - l) / 2; modify(l, mid, where, delta, 2 * node + 1); modify(mid + 1, r, where, delta, 2 * node + 2); seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]); } Node query(int ql, int qr, int l, int r, int node) { if (l > qr || r < ql) return Node(); if (l >= ql && r <= qr) return seg[node]; const int mid = l + (r - l) / 2; Node esq = query(ql, qr, l, mid, 2 * node + 1); Node dir = query(ql, qr, mid + 1, r, 2 * node + 2); Node ans; ans.merge(esq, dir); return ans; } public: void build(const vector<int> &arr) { LO = 0; HI = (int) arr.size() - 1; seg.clear(); seg.resize(4 * (int)arr.size()); build(LO, HI, 0, arr); } void modify(int where, int delta) { modify(LO, HI, where, delta, 0); } pair<int, int> query(int ql, int qr) { Node ans = query(ql, qr, LO, HI, 0); return {ans.mn, ans.mx}; } }; SegmentTree linhas, colunas; int r, c; vector<pair<int, int>> where; void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { ios::sync_with_stdio(0); cin.tie(0); r = H; c = W; linhas.build(R); colunas.build(C); where.resize(r * c); for (int i = 0; i < r * c; i++) { where[i] = {R[i], C[i]}; } } int solve() { int res = 0; int min_row = 1e9; int max_row = -1e9; int min_column = 1e9; int max_column = -1e9; for (int i = 0; i < r * c; ) { pair<int, int> line = linhas.query(0, i); min_row = min(min_row, line.first); max_row = max(max_row, line.second); pair<int, int> col = colunas.query(0, i); min_column = min(min_column, col.first); max_column = max(max_column, col.second); const int cur = ((max_row - min_row + 1) * (max_column - min_column + 1)); if (cur == i + 1) { ++res; ++i; } else { i = cur - 1; } } return res; } int swap_seats(int a, int b) { const int a_linha = where[a].first; const int b_linha = where[b].first; linhas.modify(a, b_linha); linhas.modify(b, a_linha); const int a_coluna = where[a].second; const int b_coluna = where[b].second; colunas.modify(a, b_coluna); colunas.modify(b, a_coluna); swap(where[a], where[b]); return solve(); }
#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...