제출 #596544

#제출 시각아이디문제언어결과실행 시간메모리
596544AlperenT자리 배치 (IOI18_seats)C++17
0 / 100
3411 ms40244 KiB
#include <bits/stdc++.h> #include "seats.h" using namespace std; const int N = 1e6 + 5, INF = 1e9 + 5; int n, h, w, ans; pair<int, int> merge(pair<int, int> a, pair<int, int> b){ return {min(a.first, b.first), max(a.second, b.second)}; } vector<int> X, Y; pair<int, int> xprefix[N], yprefix[N]; void give_initial_chart(int H, int W, vector<int> X_, vector<int> Y_) { X = X_, Y = Y_; X.insert(X.begin(), -1); Y.insert(Y.begin(), -1); n = H * W; xprefix[0] = {INF, -INF}, yprefix[0] = {INF, -INF}; for(int i = 1; i <= n; i++) xprefix[i] = merge(xprefix[i - 1], {X[i], X[i]}); for(int i = 1; i <= n; i++) yprefix[i] = merge(yprefix[i - 1], {Y[i], Y[i]}); for(int i = 1; i <= n; i++) if((xprefix[i].second - xprefix[i].first + 1) * (yprefix[i].second - yprefix[i].first + 1) == i) ans++; } int swap_seats(int a, int b){ a++, b++; swap(X[a], X[b]); swap(Y[a], Y[b]); for(int i = a; i <= b; i++){ if((xprefix[i].second - xprefix[i].first + 1) * (yprefix[i].second - yprefix[i].first + 1) == i) ans--; xprefix[i] = merge(xprefix[i - 1], {X[i], X[i]}); merge(yprefix[i - 1], {Y[i], Y[i]}); if((xprefix[i].second - xprefix[i].first + 1) * (yprefix[i].second - yprefix[i].first + 1) == i) ans++; } return ans; }
#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...