fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #pragma GCC optimize("Ofast, unroll-loops")
  4. #define int long long
  5. typedef long long ll;
  6.  
  7. void File() {
  8. #ifndef ONLINE_JUDGE
  9.     freopen("input.txt", "r", stdin);
  10.     freopen("output.txt", "w", stdout);
  11. #endif
  12.     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  13. }
  14.  
  15. const ll ign = 1e18;
  16. struct Node {
  17.     ll mn;
  18. };
  19.  
  20. vector<vector<Node> > pre;
  21.  
  22. Node merge(Node a, Node b) {
  23.     return {min(a.mn, b.mn)};
  24. }
  25.  
  26. Node query(int l, int r) { // Not Idempotent --> O(Log (r-l+1))
  27.     int sz = r - l + 1;
  28.     Node ans = {ign};
  29.     for (int i = 0; (1 << i) <= sz; ++i) {
  30.         if ((1 << i) & sz) {
  31.             ans = merge(ans, pre[i][l]);
  32.             l += (1 << i);
  33.         }
  34.     }
  35.     return ans;
  36. }
  37.  
  38. Node queryO1(int l, int r) {
  39.     // Idempotent --> O(1)
  40.     int sz = 31 - __builtin_clz(r - l + 1);
  41.     return merge(pre[sz][l], pre[sz][r - (1 << sz) + 1]);
  42. }
  43.  
  44. void SparseTable(int n, vector<int> &v) {
  45.     for (int i = 0; i < n; ++i)
  46.         pre[0][i] = {v[i]};
  47.     for (int i = 1; (1 << i) <= n; ++i) {
  48.         for (int j = 0; j + (1 << i) <= n; ++j) {
  49.             pre[i][j] = merge(pre[i - 1][j], pre[i - 1][j + (1 << (i - 1))]);
  50.         }
  51.     }
  52. }
  53.  
  54. void sol() {
  55.     int n;
  56.     cin >> n;
  57.     vector<pair<int, int>> v(n);
  58.     map<int, int> mp;
  59.     for(int i = 0; i < n; ++i) {
  60.         cin >> v[i].first >> v[i].second;
  61.         mp[v[i].first]++;
  62.         mp[v[i].second]++;
  63.     }
  64.     int c = 0;
  65.     for(auto& [a, b] : mp) {
  66.         mp[a] = c++;
  67.     }
  68.     for(int i = 0; i < n; ++i) {
  69.         v[i].first = mp[v[i].first];
  70.         v[i].second = mp[v[i].second];
  71.     }
  72.     vector<int> pref(c+2);
  73.     for(int i = 0; i < n; ++i) {
  74.         pref[v[i].first]++;
  75.         pref[v[i].second+1]--;
  76.     }
  77.     for(int i = 1; i <= c; ++i) {
  78.         pref[i] += pref[i-1];
  79.     }
  80.     pre.assign(31 - __builtin_clz(c+2)+1, vector<Node>(c+2));
  81.     SparseTable(c+2,pref);
  82.     for(int i = 0; i < n; ++i) {
  83.         if(queryO1(v[i].first, v[i].second).mn > 1) {
  84.             cout << i+1 << '\n';
  85.             return;
  86.         }
  87.     }
  88.     cout << -1 << '\n';
  89. }
  90.  
  91. signed main() {
  92.     File();
  93.     int T{1};
  94.     //cin >> T;
  95.     while (T--) {
  96.         sol();
  97.     }
  98. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/XVxBLS
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!