제출 #800206

#제출 시각아이디문제언어결과실행 시간메모리
800206Josia자리 배치 (IOI18_seats)C++17
0 / 100
366 ms175104 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; struct seg { struct node { int iMin = 1e9, iMax = -1e9, jMin = 1e9, jMax = -1e9; }; node op(node a, node b) { node res; res.iMin = min(a.iMin, b.iMin); res.iMax = min(a.iMax, b.iMax); res.jMin = min(a.jMin, b.jMin); res.jMax = min(a.jMax, b.jMax); return res; } vector<node> tree; void update(int v, int rl, int rr, int pos, int i, int j) { if (rl == rr) { tree[v].iMax = i; tree[v].iMin = i; tree[v].jMax = j; tree[v].jMin = j; return; } int rm = (rl + rr)/2; if (pos <= rm) update(v*2, rl, rm, pos, i, j); else update(v*2+1, rm+1, rr, pos, i, j); tree[v] = op(tree[v*2], tree[v*2+1]); } node query(int v, int rl, int rr, int ql, int qr) { if (ql > qr) return node(); if (rl == ql && rr == qr) return tree[v]; int rm = (rl + rr)/2; return op(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr)); } void init(int n, vector<pair<int, int>> ass) { tree.resize(n*4); for (int i = 0; i<n; i++) { update(1, 0, n-1, i, ass[i].first, ass[i].second); } } }; seg tree; int n; vector<pair<int, int>> seating; void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { n = H*W; seating.resize(n); for (int i = 0; i<n; i++) { seating[i].first = R[i]; seating[i].first = C[i]; } tree.init(n, seating); } int swap_seats(int a, int b) { tree.update(1, 0, n-1, a, seating[b].first, seating[b].second); tree.update(1, 0, n-1, b, seating[a].first, seating[a].second); swap(seating[a], seating[b]); int res = 0; for (int i = 0; i<n; i++) { auto blub = tree.query(1, 0, n-1, 0, i); int field = (blub.iMax-blub.iMin+1)*(blub.jMax-blub.jMin+1); assert(field>i); if (field == i+1) res++; else i = field-1; } return res; }
#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...