Submission #963031

#	Time	Username	Problem	Language	Result	Execution time	Memory
963031		PenguinsAreCute	Strange Device (APIO19_strange_device)	C++17	100 / 100	1481 ms	53888 KiB

strange_device

// 34 days to apio!
#include <bits/stdc++.h>
using namespace std;
#define int long long
main() {
	int n, a, b, p; cin >> n >> a >> b;
	a /= __gcd(a,b+1);
	if(a>1e18/b) p=1e18;
	else p=a * b;
	vector<pair<int,int>> v;
	for(int i=0;i<n;i++) {
		int l, r; cin >> l >> r;
		if(r-l>p) {cout<<p; return 0;}
		else if(l/p == r/p) v.push_back({l%p,r%p});
		else {
			v.push_back({l%p,p-1});
			v.push_back({0,r%p});
		}
	}
	sort(v.begin(),v.end(),greater<pair<int,int>>());
	int ans = 0;
	while(v.size()>=2) {
		if(end(v)[-2].first<=end(v)[-1].second) end(v)[-2]={end(v)[-1].first,max(end(v)[-1].second,end(v)[-2].second)};
		else ans += end(v)[-1].second-end(v)[-1].first+1;
		v.pop_back();
	}
	cout << ans + v[0].second - v[0].first + 1;
}

Compilation message (stderr)

strange_device.cpp:5:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    5 | main() {
      | ^~~~

• 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