Submission #732057

#	Time	Username	Problem	Language	Result	Execution time	Memory
732057		US3RN4M3	Strange Device (APIO19_strange_device)	C++17	35 / 100	1728 ms	51088 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, A, B;
vector<pair<ll, ll>> segs;
void solve2() {
	ll ans = 0;
	for(auto & [l, r] : segs) {
		cin >> l >> r;
		ans += r - l + 1;
	}
	cout << ans << endl;
}

ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}

//x(B+1) == 0
//x(b+1)
main() {
	cin >> n >> A >> B;
	segs.resize(n);
	ll C = A / (gcd(B + 1, A));
	assert(C);
	__int128 X = C;
	__int128 Y = B;
	__int128 Z = C * B;
	if(Z >= 1e18 + 10) {
		solve2();
		return 0;
	}
	ll cycle = C * B;
	vector<pair<ll, bool>> evt;
	for(auto & [l, r] : segs) {
		cin >> l >> r;
		r++;
		if(l >= cycle) {
			ll tmp = (l / cycle) * cycle;
			l -= tmp;
			r -= tmp;
		}
		if(r >= cycle*2) {
			cout << cycle << endl;
			return 0;
		}
		if(r >= cycle) {
			evt.push_back({l, true});
			evt.push_back({0, true});
			evt.push_back({r - cycle, false});
		} else {
			evt.push_back({l, true});
			evt.push_back({r, false});
		}
	}
	sort(evt.begin(), evt.end());
	ll prev = 0;
	int cnt = 0;
	ll ans = 0;
	for(auto [t, b] : evt) {
		ll delta = t - prev;
		prev = t;
		if(cnt > 0) ans += delta;
		if(b) cnt++;
		else cnt--;
	}
	if(cnt > 0) ans += cycle - prev;
	cout << ans << endl;
}

Compilation message (stderr)

strange_device.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main() {
      | ^~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:26:11: warning: unused variable 'X' [-Wunused-variable]
   26 |  __int128 X = C;
      |           ^
strange_device.cpp:27:11: warning: unused variable 'Y' [-Wunused-variable]
   27 |  __int128 Y = B;
      |           ^

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