Submission #409811

#	Time	Username	Problem	Language	Result	Execution time	Memory
409811		kwongweng	Strange Device (APIO19_strange_device)	C++17	65 / 100	571 ms	35388 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define F first
#define S second
ll MOD = 1000000007;
ll INF = 1000000000;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
	if (a == 0) return b;
	if (a == 1) return 1;
	return gcd(b%a, a);
}

int check(ll n){
	ll m = n;
	int cnt = 0;
	while (m > 0){
		m /= 2;
		cnt++;
	}
	return cnt;
}
ll len = MOD*MOD;
int main(){
    ios::sync_with_stdio(false);
    int n; cin >> n;
    ll a, b; cin >> a >> b;
    ll c = a / gcd(a, b+1);
    if (check(b) + check(c) < 63){
    	len = b*c;
	}
	vector<pll> range;
	FOR(i, 0, n){
		ll l, r; cin >> l >> r;
		l%=len; r%=len;
		if (l > r){
			range.pb({0, r%len});
			range.pb({l%len, len-1});
		}else{
			range.pb({l, r});
		}
	}
	sort(range.begin(), range.end());
	ll ans = 0;
	ll l = range[0].F; ll r = range[0].S;
	FOR(i, 0, range.size()){
		if (range[i].F - r > 1){
			ans += r - l + 1;
			l = range[i].F; r = range[i].S;
			continue;
		}
		r = max(range[i].S, r);
	}
	ans += r - l + 1;
	cout << ans << '\n';
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:9:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
   76 |  FOR(i, 0, range.size()){
      |      ~~~~~~~~~~~~~~~~~~                
strange_device.cpp:76:2: note: in expansion of macro 'FOR'
   76 |  FOR(i, 0, range.size()){
      |  ^~~

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