Submission #231112

#	Time	Username	Problem	Language	Result	Execution time	Memory
231112		ChrisT	Strange Device (APIO19_strange_device)	C++17	100 / 100	606 ms	41368 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pib = pair<int,bool>;
using ll = long long;
using pll = pair<ll,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#ifdef fread_unlocked
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#endif
#define lc ind<<1
#define rc ind<<1|1
const int MN = 25e4+4, MOD = 1e9+7, BASE = 31;
int main () {
	int n; ll a,b;
	scanf ("%d %lld %lld",&n,&a,&b);
	ll x = a/__gcd(a,b+1);
	__int128 pp = (__int128)b*x;
	ll p = (ll)min(pp,__int128(1e18+2));
	vector<pll> segs;
	while (n--) {
		ll l,r;
		scanf ("%lld %lld",&l,&r); if (r-l+1 >= p) return !printf ("%lld\n",p);
		ll nxt = (l/p+1)*p;
		if (nxt <= r) {
			segs.emplace_back(l%p,(nxt-1)%p); segs.emplace_back(nxt%p,r%p);
		} else segs.emplace_back(l%p,r%p);
	}
	sort(all(segs));
	ll lr = -2; ll ret = 0;
	for (auto &[l,r] : segs) {
		if (r > lr) {
			ret += r-max(lr+1,l)+1;
			lr = r;
		}
	}
	printf ("%lld\n",ret);
	return 0;
}
/*
find period:
find first t>0 s/t t%b==0 && (t+t/b)%a==0
since b|t let t = xb for some minimal x
(xb+xb/b)%a == 0
(xb+x)%a==0
(x(b+1))%a==0
b+1 is constant, cancel out gcd(a,b+1)
x = a/gcd(a,b+1)
t = ba/gcd(a,b+1)
*/

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %lld %lld",&n,&a,&b);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:25:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%lld %lld",&l,&r); if (r-l+1 >= p) return !printf ("%lld\n",p);
   ~~~~~~^~~~~~~~~~~~~~~~~~~

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