fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6. inline int power(int a, int b) {
  7.     int x = 1;
  8.     while (b) {
  9.         if (b & 1) x *= a;
  10.         a *= a;
  11.         b >>= 1;
  12.     }
  13.     return x;
  14. }
  15.  
  16.  
  17. const int M = 1000000007;
  18. const int N = 3e5+9;
  19. const int INF = 2e9+1;
  20. const int LINF = 2000000000000000001;
  21.  
  22. //_ ***************************** START Below *******************************
  23.  
  24.  
  25. //_ Intuition : 
  26. //* Bruteforce : 
  27. //*     Iterate each query from q1 to qn
  28. //*     Build State[n] array of 0's and fill it with queries [q0 to qi] in O(q) time
  29. //*     Iterate each segment and find out any segments with 1's > segLen/2  in O(m) time
  30. //*     To check 1's in Seg_i in O(1) time, 
  31. //*         Build prefixSum[] of State[] to get sum of range [l,r] in O(1) 
  32. //*         This takes O(n) time
  33. //*     Hence T.C. == O(q * (q+m+n))
  34.  
  35. //*     We can notice that once Seg becomes beautiful for qi query, 
  36. //*         It remains beautiful for qi+1 to qn queries also
  37. //*     Monotonic Predicate func Property 
  38.  
  39. //*     Hence we can use Binary Search on Outer Linear Search 
  40. //*         logq * ( q + m + n)
  41.  
  42. //_ T.C. : 
  43. //*     O(logq * (q + m + n))
  44.  
  45.  
  46. vector<pair<int,int>> segs;
  47. vector<int> q;
  48. int n;
  49. int m;
  50. int k;
  51.  
  52. bool isPossible(int mid){
  53.  
  54.     vector<int> temp(n, 0);
  55.     for(int i=0; i<=mid; i++){
  56.         int idx = q[i];
  57.         temp[idx-1] = 1;
  58.     }
  59.  
  60.     vector<int> prefix(n+1, 0);
  61.     for(int i=0; i<n; i++){
  62.         prefix[i+1] = prefix[i] + temp[i];
  63.     }
  64.  
  65.     for(int i=0; i<m; i++){
  66.         int l = segs[i].first;
  67.         int r = segs[i].second;
  68.  
  69.         int ones = prefix[r] - prefix[l-1];
  70.  
  71.         if(ones > (r-l+1)/2) return true;
  72.  
  73.     }
  74.     return false;
  75.  
  76. }
  77.  
  78. int consistency(){
  79.     int ans = INF;
  80.     int s = 0, e = k-1;
  81.     while(s<=e){
  82.         int mid = s + (e-s)/2;
  83.         if(isPossible(mid)){
  84.             ans = min(ans, mid);
  85.             e = mid-1;
  86.         }
  87.         else{
  88.             s = mid+1;
  89.         }
  90.  
  91.     }
  92.  
  93.     if(ans == INF) return -1;
  94.     return ans+1;
  95.  
  96. }
  97.  
  98. void solve() {
  99.  
  100.     cin>>n >> m;
  101.     segs.resize(m);
  102.     for(int i=0; i<m; i++){
  103.         int x, y;
  104.         cin >> x >> y;
  105.         segs[i] = {x,y};
  106.     }
  107.     cin >> k;
  108.     q.resize(k);
  109.     for(int i=0; i<k; i++) cin >> q[i];
  110.     cout << consistency() << endl;
  111.  
  112.  
  113. }
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120. int32_t main() {
  121.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  122.  
  123.     int t = 1;
  124.     cin >> t;
  125.     while (t--) {
  126.         solve();
  127.     }
  128.  
  129.     return 0;
  130. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
6
5 5
1 2
4 5
1 5
1 3
2 4
5
5
3
1
2
4
4 2
1 1
4 4
stdout
copy 
3
3
5
5
5
5
https://ideone.com/ncOLdV
language:
C++14 (gcc 8.3)
created:
1 day 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!