Submission #172105

#	Time	Username	Problem	Language	Result	Execution time	Memory
172105		super_j6	Strange Device (APIO19_strange_device)	C++14	100 / 100	802 ms	53304 KiB

strange_device

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define pi pair<long long, long long>

const long long inf = 2000000000000000000;
const int maxn = 2000001;
long long n, m, a, b;
pi p[maxn];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> a >> b;
	m = __gcd(b + 1, a) % a;
	m += a * (m == 0);
	m = min(inf / b, a / m) * b;
	
	for(int i = 0; i < n; i++){
		cin >> p[i].first >> p[i].second;
		if(p[i].second - p[i].first >= m) p[i] = {0, m - 1};
		p[i].first %= m, p[i].second %= m;
		if(p[i].second < p[i].first){
			p[i + 1] = {p[i].first, m - 1};
			p[i].first = 0;
			i++, n++;
		}
	} 
	
	p[n] = {m, m};
	sort(p, p + n);
	
	long long ret = 0;
	for(long long i = 0, j = p[0].second, k = p[0].first; i < n; i++){
		j = max(j, p[i].second);
		if(j < p[i + 1].first){
			ret += j - k + 1;
			k = p[i + 1].first;
		}
	}
	
	cout << ret << endl;
	
	return 0;
}

• 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