Submission #361924

#	Time	Username	Problem	Language	Result	Execution time	Memory
361924		RohamIzadidoost	Strange Device (APIO19_strange_device)	C++14	0 / 100	1 ms	364 KiB

strange_device

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
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);
}
const int maxn = 1000*1000+5 ;
const ll inf = 4223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
ll n , a  , b  , l , r , L , R , ans , p , w, k ; 
set<pll> s ; 
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 ; 
	cout<<"p : " << p << endl ; 
	while(n--){
		cin>>l>>r ;
		if(k) continue ;
		if(r - l + 1 >= p ){
			k = 1 ;
			ans = p ; 
			continue ; 
		} 
		l = l % p ; 
		r = r % p ; 
	//	cout<<n <<" : " << endl ; 
		if(r >= l){
			s.insert({l , r}) ; 
		//	cout<<l<<","<<r << endl ; 
		}else{
			s.insert({0 , r}) ; 
			s.insert({l , p - 1}) ; 
		//	cout<<0 <<","<<r <<" & " <<l <<","<<p-1 << endl ; 
		}
	} 
	if(k){
		cout<<ans ; 
		return 0; 
	}
	s.insert({inf + 1 , inf  + 1}) ; 
	L = s.begin() -> X , R = s.begin() -> Y ; 
	auto it = next(s.begin()) ;
	while(it != s.end()){
		if(it -> X > R){
			ans += R - L + 1 ; 
			//cout<<" ad " << L <<" , " << R << endl ; 
			L = it -> X , R = it -> Y ; 
		}else{
			R = max(R , it -> Y) ; 
		}
		it++ ; 
	} 
	cout<<ans << endl ; 
}

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