fork(1) download
copy 
  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long 
  5. #define mod 1000000007
  6. #define inf (int)1e9
  7. #define pb(a) push_back(a)
  8. #define mem(a, b) memset(a, (b), sizeof(a))
  9. #define p pair<int,int>
  10. // ll modpow(ll x,ll n,int M){ll result=1;while(n>0){if(n&1){result=(result * x)%M;}x=(x*x)%M;n=n>>1;}return result;}
  11. // ll mod_mul(ll x,ll y,int M){return ((x%M)*(y%M))%M;}
  12. /////////////////////////////////////////////////
  13.  
  14.  
  15. bool ispossible(vector<pair<int,int>>&v,int mid,int n){
  16.  
  17.     priority_queue<p,vector<p>,greater<p>>pq;
  18.  
  19.     int i=0;
  20.     int s=1;
  21.     while(i<v.size()&&s<n){
  22.  
  23.         while(i<v.size()&&v[i].first<=s){
  24.  
  25.             pq.push({v[i].second,v[i].first});
  26.             i++;
  27.         } 
  28.         if(pq.empty()) return false;
  29.  
  30.         auto x= pq.top();
  31.         s=min(x.first,s+mid);
  32.         pq.pop();
  33.        while( !pq.empty()&&pq.top().first<=s) pq.pop();
  34.  
  35.     }
  36.  
  37.    return s==n;
  38.  
  39. }
  40.  
  41.  
  42.  
  43. int main(){
  44.  ios_base::sync_with_stdio(false);cin.tie(NULL);
  45.  
  46.  
  47.    int t;
  48.    cin>>t;
  49.    while(t--){
  50.     int n,m,l,r;
  51.     cin>>n>>m;
  52.     vector<pair<int,int>>v;
  53.  
  54.     int right =INT_MIN;
  55.     for(int i=0;i<m;i++){
  56.       cin>>l>>r;
  57.       v.push_back({l,r});
  58.  
  59.       right =max(right,r-l);
  60.  
  61.     }
  62.  
  63.  
  64.     sort(begin(v),end(v));
  65.     int left=1;
  66.     int ans=-1;
  67.     right=1e9;
  68.  
  69.     while(left<=right){
  70.  
  71.        int mid = left+ (right-left)/2;
  72.  
  73.        if(ispossible(v,mid,n)){
  74.         ans=mid;
  75.         right=mid-1;
  76.        }else{
  77.         left=mid+1;
  78.        }
  79.  
  80.     }
  81.  
  82.     cout<<ans<<"\n";
  83.  
  84.  
  85.  
  86.  
  87.    }
  88.   return 0;
  89. }
Success #stdin #stdout 0.01s 5408KB
comments (?)
stdin
copy 
3
10 3
1 10
1 5
6 10
10 1
2 10
10 2
5 10
1 5
stdout
copy 
3
-1
5
https://ideone.com/KAvNeQ
language:
C++14 (gcc 8.3)
created:
3 years 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!