fork download
copy 
  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 int ign = 2e9;
  16.  
  17. struct Node {
  18.     int mn;
  19. };
  20.  
  21. vector<vector<Node> > pre;
  22.  
  23. Node merge(Node a, Node b) {
  24.     return {min(a.mn, b.mn)};
  25. }
  26.  
  27. Node query(int l, int r) {
  28.     // Not Idempotent --> O(Log (r-l+1))
  29.     int sz = r - l + 1;
  30.     Node ans = {ign};
  31.     for (int i = 0; (1 << i) <= sz; ++i) {
  32.         if ((1 << i) & sz) {
  33.             ans = merge(ans, pre[i][l]);
  34.             l += (1 << i);
  35.         }
  36.     }
  37.     return ans;
  38. }
  39.  
  40. Node queryO1(int l, int r) {
  41.     // Idempotent --> O(1)
  42.     int sz = 31 - __builtin_clz(r - l + 1);
  43.     return merge(pre[sz][l], pre[sz][r - (1 << sz) + 1]);
  44. }
  45.  
  46. void SparseTable(int n, vector<int> &v) {
  47.     for (int i = 0; i < n; ++i)
  48.         pre[0][i] = {v[i]};
  49.     for (int i = 1; (1 << i) <= n; ++i) {
  50.         for (int j = 0; j + (1 << i) <= n; ++j) {
  51.             pre[i][j] = merge(pre[i - 1][j], pre[i - 1][j + (1 << (i - 1))]);
  52.         }
  53.     }
  54. }
  55.  
  56. void sol() {
  57.     int n;
  58.     cin >> n;
  59.     vector<pair<int, int>> v(n);
  60.     map<int, int> mp;
  61.     for(int i = 0; i < n; ++i) {
  62.         cin >> v[i].first >> v[i].second;
  63.         mp[v[i].first] = 1;
  64.         mp[v[i].second] = 1;
  65.         mp[v[i].second+1] = 1;
  66.     }
  67.     int c = 1;
  68.     for(auto& [a, b] : mp) {
  69.         mp[a] = c++;
  70.     }
  71.     for(int i = 0; i < n; ++i) {
  72.         v[i].first = mp[v[i].first];
  73.         v[i].second = mp[v[i].second];
  74.     }
  75.     vector<int> pref(c+10);
  76.     for(int i = 0; i < n; ++i) {
  77.         pref[v[i].first]++;
  78.         pref[v[i].second+1]--;
  79.     }
  80.     for(int i = 1; i <= c+5; ++i) {
  81.         pref[i] += pref[i-1];
  82.     }
  83.     pre.assign(31 - __builtin_clz(c+10)+1, vector<Node>(c+10));
  84.     SparseTable(c+10,pref);
  85.     vector<vector<Node>> tmp = pre;
  86.     for(int i = 0; i < n; ++i) {
  87.         if(queryO1(v[i].first, v[i].second).mn > 1) {
  88.             cout << i+1 << '\n';
  89.             return;
  90.         }
  91.     }
  92.     cout << -1 << '\n';
  93. }
  94.  
  95. signed main() {
  96.     File();
  97.     int T{1};
  98.     //cin >> T;
  99.     while (T--) {
  100.         sol();
  101.     }
  102. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/ek22ap
language:
C++14 (gcc 8.3)
created:
4 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!