// https://sio2.mimuw.edu.pl/c/pa-2025-1/p/szk/ #include <bits/stdc++.h> #define st first #define nd second #define pb push_back #define all(x) x.begin(), x.end() #define rep(i, a) for (int i = 0; i < int(a); i++) #define rep1(i, a) for (int i = 1; i <= int(a); i++) #define los(a, b) (rng() % (int)(b - a + 1) + (int)(a)) using namespace std; typedef long long ll; typedef pair<ll, ll> pi; const int MAXN = 1; int main() { cin.tie(0)->sync_with_stdio(0); ll n, m, s; cin >> n >> m >> s; vector<pi> v(m); rep(i, m) cin >> v[i].st >> v[i].nd; sort(all(v)); stack<pi> seg; for (auto [a, b] : v) { if (seg.empty()) { seg.push({a, b}); continue; } auto [c, d] = seg.top(); if (a <= d + 1) { seg.pop(); seg.push({c, max(b, d)}); } else seg.push({a, b}); } ll res = 1e18; ll pos = 1e18; while (seg.size()) { auto [a, b] = seg.top(); // cerr << a << ' ' << b << '\n'; seg.pop(); if (a > 1) { if (res > abs(a - 1 - s) || (res == abs(a - 1 - s) && pos > a - 1)) { res = abs(a - 1 - s); pos = a - 1; // cerr << ' ' << abs(a - 1 - s) << ' ' << pos << '\n'; } } if (b < n) { if (res > abs(b + 1 - s) || (res == abs(b + 1 - s) && pos > b - 1)) { res = abs(b + 1 - s); pos = b + 1; // cerr << " " << abs(b + 1 - s) << ' ' << pos << '\n'; } } } cout << pos << '\n'; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | // https://sio2.mimuw.edu.pl/c/pa-2025-1/p/szk/ #include <bits/stdc++.h> #define st first #define nd second #define pb push_back #define all(x) x.begin(), x.end() #define rep(i, a) for (int i = 0; i < int(a); i++) #define rep1(i, a) for (int i = 1; i <= int(a); i++) #define los(a, b) (rng() % (int)(b - a + 1) + (int)(a)) using namespace std; typedef long long ll; typedef pair<ll, ll> pi; const int MAXN = 1; int main() { cin.tie(0)->sync_with_stdio(0); ll n, m, s; cin >> n >> m >> s; vector<pi> v(m); rep(i, m) cin >> v[i].st >> v[i].nd; sort(all(v)); stack<pi> seg; for (auto [a, b] : v) { if (seg.empty()) { seg.push({a, b}); continue; } auto [c, d] = seg.top(); if (a <= d + 1) { seg.pop(); seg.push({c, max(b, d)}); } else seg.push({a, b}); } ll res = 1e18; ll pos = 1e18; while (seg.size()) { auto [a, b] = seg.top(); // cerr << a << ' ' << b << '\n'; seg.pop(); if (a > 1) { if (res > abs(a - 1 - s) || (res == abs(a - 1 - s) && pos > a - 1)) { res = abs(a - 1 - s); pos = a - 1; // cerr << ' ' << abs(a - 1 - s) << ' ' << pos << '\n'; } } if (b < n) { if (res > abs(b + 1 - s) || (res == abs(b + 1 - s) && pos > b - 1)) { res = abs(b + 1 - s); pos = b + 1; // cerr << " " << abs(b + 1 - s) << ' ' << pos << '\n'; } } } cout << pos << '\n'; } |