#include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define st first #define nd second #define fi first #define se second #define vt vector #define FOR(a, b, c) for(int a=b; a<c; ++a) #define all(a) (a).begin(),(a).end() #define sz(a) (int)(a).size() typedef long long ll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; typedef pii PII; typedef pll PLL; constexpr ll nax = 2e5+6969, INF = 1e9+2137; constexpr ld eps = 1e-9; mt19937_64 rng(6969); // mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); inline ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } ll n, m, s; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> s; vector<pll> v(m); for(auto &e: v) { cin >> e.fi >> e.se; } sort(all(v)); ll dis = n * 2; ll ans = -1; for(int i = 0; i < m; i++) { if(s > v[i].se) continue; int cur = i; while(cur > 0 && v[cur-1].se + 1 == v[cur].fi) cur--; if(v[cur].fi > 1) { if(dis > s - (v[cur].fi - 1)) { dis = s - (v[cur].fi - 1); ans = v[cur].fi - 1; } } cur = i; while(cur < m && v[cur+1].fi - 1 == v[cur].se) cur++; if(v[cur].se < n) { if(dis > (v[cur].se + 1) - s) { dis = (v[cur].se + 1) - s; ans = v[cur].se + 1; } } break; } cout << ans << "\n"; return 0; }
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define st first #define nd second #define fi first #define se second #define vt vector #define FOR(a, b, c) for(int a=b; a<c; ++a) #define all(a) (a).begin(),(a).end() #define sz(a) (int)(a).size() typedef long long ll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; typedef pii PII; typedef pll PLL; constexpr ll nax = 2e5+6969, INF = 1e9+2137; constexpr ld eps = 1e-9; mt19937_64 rng(6969); // mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); inline ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } ll n, m, s; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> s; vector<pll> v(m); for(auto &e: v) { cin >> e.fi >> e.se; } sort(all(v)); ll dis = n * 2; ll ans = -1; for(int i = 0; i < m; i++) { if(s > v[i].se) continue; int cur = i; while(cur > 0 && v[cur-1].se + 1 == v[cur].fi) cur--; if(v[cur].fi > 1) { if(dis > s - (v[cur].fi - 1)) { dis = s - (v[cur].fi - 1); ans = v[cur].fi - 1; } } cur = i; while(cur < m && v[cur+1].fi - 1 == v[cur].se) cur++; if(v[cur].se < n) { if(dis > (v[cur].se + 1) - s) { dis = (v[cur].se + 1) - s; ans = v[cur].se + 1; } } break; } cout << ans << "\n"; return 0; } |