| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 609794 | MohamedFaresNebili | Seats (IOI18_seats) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
int H, W;
int X[2][4000004], Y[2][4000004];
vector<int> R, C;
void build(int v, int l, int r, int t) {
if(l == r) {
X[t][v] = Y[t][v] = (t == 0 ? R[l] : C[l]);
return;
}
build(v * 2, l, (l + r) / 2);
build(v * 2 + 1, (l + r) / 2 + 1, r);
X[t][v] = min(X[t][v * 2], X[t][v * 2 + 1]);
Y[t][v] = max(Y[t][v * 2], Y[t][v * 2 + 1]);
}
void update(int v, int l, int r, int p, int val, int t) {
if(l == r) {
X[t][v] = Y[t][v] = val;
return;
}
int md = (l + r) / 2;
if(p <= md) update(v * 2, l, md, p, val, t);
else update(v * 2 + 1, md + 1, r, p, val, t);
X[t][v] = min(X[t][v * 2], X[t][v * 2 + 1]);
Y[t][v] = max(Y[t][v * 2], Y[t][v * 2 + 1]);
}
pair<int, int> query(int v, int l, int r, int lo, int hi, int t) {
if(l > hi || r < lo) return {-1, -1};
if(l >= lo && r <= hi) return {X[t][v], Y[t][v]};
pair<int, int> A = query(v * 2, l, (l + r) / 2, lo, hi, t);
pair<int, int> B = query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, t);
if(A.first == -1) return B;
if(B.first == -1) return A;
return {min(A.first, B.first), max(A.second, B.second)};
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
::H = H; ::W = W;
for(auto u : R) ::R.push_back(u);
for(auto u : C) ::C.push_back(u);
build(1, 0, H * W - 1, 0);
build(1, 0, H * W - 1, 1);
}
int swap_seats(int A, int B) {
swap(R[A], R[B]); swap(C[A], C[B]);
update(1, 0, H * W - 1, A, R[A], 0);
update(1, 0, H * W - 1, A, C[A], 1);
update(1, 0, H * W - 1, B, R[B], 0);
update(1, 0, H * W - 1, B, C[B], 1);
int res = 0;
for(int l = 0; l < H * W; ) {
pair<int, int> U = query(1, 0, H * W - 1, 0, l, 0);
pair<int, int> V = query(1, 0, H * W - 1, 0, l, 1);
int cur = (U.second - U.first + 1) * (V.second - V.first + 1);
res += (cur == l + 1);
if(cur == l + 1) l += min(U.second - U.first + 1, V.second - V.first + 1);
else l = cur - 1;
}
return res;
}