Submission #363258

#	Time	Username	Problem	Language	Result	Execution time	Memory
363258		armanmohammadi	Strange Device (APIO19_strange_device)	C++14	20 / 100	634 ms	47536 KiB

strange_device

/*
 _________        .---"""      """---.
:______.-':      :  .--------------.  :
| ______  |      | :                : |
|:______B:|      | |  Little Error: | |
|:______B:|      | |                | |
|:______B:|      | |  Power not     | |
|         |      | |  found.        | |
|:_____:  |      | |                | |
|    ==   |      | :                : |
|       O |      :  '--------------'  :
|       o |      :'---...______...---'
|       o |-._.-i___/'             \._
|'-.____o_|   '-.   '-...______...-'  `-._
:_________:      `.____________________   `-.___.-.
                 .'.eeeeeeeeeeeeeeeeee.'.      :___:
    fsc        .'.eeeeeeeeeeeeeeeeeeeeee.'.
              :____________________________:
*/




//in the name of god
//if you read this code please search about imam hussain
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define endl "\n"
#define X first
#define Y second
#define pii pair<int,int>
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)
const int maxn=2e5+5;
const int mod=1e9+7;
const int inf=1e9;
const int del=728729;
const int Pr2 = 1030294297 ;
ll poww(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));}
ll gcd(ll a, ll b) {
   if (b == 0){
      return a;   	
   }

   return gcd(b, a % b);
}

set<pii> st ; 
ll n ;
ll a  ;
ll b  ;
ll l ;
ll r ;
ll lp ;
ll rp ;
ll ans ;
ll p ;
ll w ;
ll k ; 
int main(){
  migmig ;
  cin >> n >> a >> b ; 
  if(a/gcd(a , b + 1) > inf / b){
  	p = inf ;
  }else{
  	p =  a / gcd(a , b + 1) * b ; 
  } 
  for(int tst=0 ; tst< n ; tst++){
    cin>>l>>r ;
    if(k){
    	continue ;
	}
    if(r - l + 1 >= p ){
      k = 1 ;
      ans = p ; 
      continue ; 
    } 
    l = l % p ; 
    r = r % p ; 
    if(r >= l){
      st.insert({l , r}) ; 
    }else{
      st.insert({0 , r}) ; 
      st.insert({l , p - 1}) ; 
    }
  }
  
  
  
  
  
  
  
  
  
   
  if(k){
    cout<<ans ; 
    return 0; 
  }
  st.insert({inf + 1 , inf  + 1}) ; 
  lp = st.begin() -> X ;
  rp = st.begin() -> Y ; 
  //cout<<lp <<" " << rp ;
  auto it = next(st.begin()) ;
  while(it != st.end()){
    if(it -> X > rp){
    	//cout<<lp <<" " << rp ;
    	ans += rp - lp + 1 ; 
    	lp = it -> X;
		rp = it -> Y ; 
		//cout<<lp <<" " << rp ;
    }else{
      rp = max(rp ,1LL* it -> Y) ;
      //cout<<lp <<" " << rp ;
    }
    it++ ; 
  } 
  cout<<ans << endl ; 
  return 0 ;
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30