# Hướng dẫn 🗿🗿🗿👆👆👆
Sử dụng 2 cấu trúc dữ liệu:
set<int>: để lưu vị trí các ngôi nhà hiện tại (tự động sắp xếp).
multiset<int>: để lưu khoảng cách giữa các ngôi nhà kề nhau — ta cần lấy giá trị nhỏ nhất trong này.
Mỗi thao tác:
Nếu xây nhà tại p:
Tìm it = S.lower_bound(p):
Nếu it không phải là begin(), chèn p - prev(it)
Nếu it != end(), chèn *it - p
Nếu cả trước và sau đều có, xóa khoảng cách cũ giữa hai nhà đó (giữa prev(it) và *it)
Nếu phá nhà tại p:
Tương tự, cập nhật lại các khoảng cách kề cũ và thêm lại khoảng cách mới nếu có
# Code:
/* code by NguyenDucTrung
addfr PunishingGrayRaven ID:13912080 */
#include <bits/stdc++.h>
#define ll long long
#define I first
#define II second
#define vi vector<int>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n;
cin >> n;
set<int> diem;
multiset<int> gaps;
while (n--) {
int p;
cin >> p;
if (!diem.count(p)) {
auto it=diem.lower_bound(p);
if (it!=diem.end()&&it!=diem.begin()) {
auto pre=prev(it);
gaps.erase(gaps.find(*it-*pre));
}
if (it!=diem.end()) {
gaps.insert(*it - p);
}
if (it!=diem.begin()) {
gaps.insert(p - *prev(it));
}
diem.insert(p);
} else {
auto it=diem.find(p);
auto nt=next(it);
auto pre=(it== diem.begin())?diem.end():prev(it);
if (nt!=diem.end()) {
gaps.erase(gaps.find(*nt-*it));
}
if (pre!=diem.end()) {
gaps.erase(gaps.find(*it-*pre));
}
if (nt!=diem.end()&&pre!=diem.end()) {
gaps.insert(*nt-*pre);
}
diem.erase(it);
}
if (diem.size()<2) cout << -1 << '\n';
else cout << *gaps.begin() << '\n';
}
return 0;
}
NguyenDucTrung
Created at
1 likes