Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <bitset>
- #include <cassert>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <list>
- #include <map>
- #include <queue>
- #include <set>
- #include <string>
- #include <sstream>
- #include <vector>
- #include <complex>
- #include <ctime>
- #include <stack>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef vector<int> VI;
- typedef vector< VI > VVI;
- typedef pair<int, int> PII;
- typedef vector<PII> VPII;
- #define REP(i, n) for(int i = 0; i < (n); ++i)
- #define RREP(i, n) for(int i = (n) - 1; i >= 0; --i)
- #define FOR(i, x, y) for(int i = (x); i <= (y); ++i)
- #define RFOR(i, x, y) for(int i = (x); i >= (y); --i)
- #define SZ(a) (int)(a).size()
- #define ALL(a) (a).begin(),(a).end()
- #define SORT(a) sort(ALL(a))
- #define CLEAR(x) memset(x, 0, sizeof x);
- #define COPY(FROM, TO) memcpy(TO, FROM, sizeof TO);
- #define UNIQUE(c) SORT(c),(c).resize(unique(ALL(c))-(c).begin())
- #define pb push_back
- #define mk make_pair
- #define sqr(x) ((x)*(x))
- #define X first
- #define Y second
- const long double pi=acos(-1.0);
- const double EPS = 1E-9;
- const int INF = (1e+9);
- const int NMAX = 31625;
- const int MOD = 1743;
- int n, k;
- vector<pair<PII, int> > arr;
- struct aaa{
- int l, r, n;
- aaa (pair<PII, int> val_) {
- l = val_.X.X;
- r = val_.X.Y;
- n = val_.Y;
- }
- bool operator< (const aaa& rhs) const {
- return r <= rhs.r;
- }
- };
- set<aaa> st;
- int main () {
- freopen ("ancient.in", "r", stdin);
- freopen ("ancient.out", "w", stdout);
- cin >> n;
- arr.resize(n);
- REP (i, n) {
- cin >> arr[i].X.X >> arr[i].X.Y;
- arr[i].Y = i;
- }
- SORT(arr);
- int minn = INF;
- int s1 = -1, s2 = -1;
- REP (i, n) {
- if (!st.empty()) {
- aaa top(*st.begin());
- int intersect = min(top.r, arr[i].X.Y) - arr[i].X.X;
- if (intersect <= 0)
- st.erase(st.begin());
- else if (minn > intersect) {
- minn = intersect;
- s1 = arr[i].Y, s2 = top.n;
- }
- }
- st.insert (aaa(arr[i]));
- }
- if (s1 < 0)
- cout << 0;
- else
- cout << s1 + 1 << " " << s2 + 1;
- }
- /*
- 6
- 1 3 5 7 11 13
- 5
- */
Advertisement
Add Comment
Please, Sign In to add comment