Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <set>
- using namespace std;
- const int INF = static_cast<int>(2e9) + 1;
- struct segment {
- int l, r;
- };
- int main() {
- int n;
- cin >> n;
- vector<segment> v(n);
- vector<pair<pair<int, int>, int>> events;
- for (int i = 0; i < n; ++i) {
- cin >> v[i].l >> v[i].r;
- events.push_back({{v[i].l, 1}, i});
- events.push_back({{v[i].r, 0}, i});
- }
- sort(events.begin(), events.end());
- set<pair<int, int>> opened;
- int ans = INF;
- int a = 0, b = 0;
- int balance = 0;
- for (int i = 0; i < 2 * n; ++i) {
- int x = events[i].first.first;
- int type = events[i].first.second;
- int index = events[i].second;
- if (type == 0) {
- if (balance > 0) ans = min(v[index].r - v[index].l, ans);
- opened.erase({v[index].l, index});
- if (!opened.empty()) {
- auto p = *(--opened.end());
- if (x - p.first < ans) {
- ans = x - p.first;
- a = index, b = p.second;
- }
- }
- } else if (type == 1) {
- opened.insert({x, index});
- }
- }
- if (ans != INF) {
- if (a > b) swap(a, b);
- cout << a + 1 << " " << b + 1 << "\n";
- } else {
- cout << "0\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement