#include <algorithm> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <deque> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define JOIN_(X, Y) X##Y #define JOIN(X, Y) JOIN_(X, Y) #define TMP JOIN(tmp, __LINE__) #define PB push_back #define SZ(x) int((x).size()) #define REP(i, n) for (int i = 0, TMP = (n); i < TMP; ++i) #define FOR(i, a, b) for (int i = (a), TMP = (b); i <= TMP; ++i) #define FORD(i, a, b) for (int i = (a), TMP = (b); i >= TMP; --i) #ifdef DEBUG #define DEB(x) (cerr << x) #else #define DEB(x) #endif typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef unsigned int uint; const int INF = 1e9 + 9; vector<pll> segments; void inline one() { ll n; int m; ll s; cin >> n >> m >> s; REP(i, m) { ll a, b; cin >> a >> b; segments.emplace_back(a, b); } segments.emplace_back(0, 0); segments.emplace_back(n + 1, n + 1); sort(segments.begin(), segments.end()); vector<ll> candidates; // ll last = -1; FOR(i, 1, SZ(segments) - 2) { ll last = segments[i - 1].second; ll next = segments[i + 1].first; const auto &[a, b] = segments[i]; if (a - 1 > last) { candidates.PB(a - 1); } if (b + 1 < next) { candidates.PB(b + 1); } } ll dist = static_cast<ll>(1e15); ll best = -1; for (auto cand : candidates) { ll temp_dist = abs(cand - s); if (temp_dist < dist) { best = cand; dist = temp_dist; } } cout << best << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(0); // int z; cin >> z; while(z--) one(); }
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 80 81 82 83 84 85 86 | #include <algorithm> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <deque> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define JOIN_(X, Y) X##Y #define JOIN(X, Y) JOIN_(X, Y) #define TMP JOIN(tmp, __LINE__) #define PB push_back #define SZ(x) int((x).size()) #define REP(i, n) for (int i = 0, TMP = (n); i < TMP; ++i) #define FOR(i, a, b) for (int i = (a), TMP = (b); i <= TMP; ++i) #define FORD(i, a, b) for (int i = (a), TMP = (b); i >= TMP; --i) #ifdef DEBUG #define DEB(x) (cerr << x) #else #define DEB(x) #endif typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef unsigned int uint; const int INF = 1e9 + 9; vector<pll> segments; void inline one() { ll n; int m; ll s; cin >> n >> m >> s; REP(i, m) { ll a, b; cin >> a >> b; segments.emplace_back(a, b); } segments.emplace_back(0, 0); segments.emplace_back(n + 1, n + 1); sort(segments.begin(), segments.end()); vector<ll> candidates; // ll last = -1; FOR(i, 1, SZ(segments) - 2) { ll last = segments[i - 1].second; ll next = segments[i + 1].first; const auto &[a, b] = segments[i]; if (a - 1 > last) { candidates.PB(a - 1); } if (b + 1 < next) { candidates.PB(b + 1); } } ll dist = static_cast<ll>(1e15); ll best = -1; for (auto cand : candidates) { ll temp_dist = abs(cand - s); if (temp_dist < dist) { best = cand; dist = temp_dist; } } cout << best << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(0); // int z; cin >> z; while(z--) one(); } |