Submission #125094

#	Time	Username	Problem	Language	Result	Execution time	Memory
125094		Just_Solve_The_Problem	Strange Device (APIO19_strange_device)	C++11	35 / 100	631 ms	17064 KiB

strange_device

#include <bits/stdc++.h>

#define ll long long
#define fr first
#define sc second
#define Ok puts("ok");

using namespace std;

const int N = (int)1e6 + 7;

ll a, b, gc;
int n;
ll maxn;
int used[N * 2];

ll gcd(ll a, ll b) {
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

main() {
	scanf("%d %lld %lld", &n, &a, &b);
	bool ok = 0;
	if (log10(a / gcd(b + 1, a)) + log10(b) > 18) {
		ok = 1;
	}
	maxn = a / gcd(b + 1, a) * b;
	ll ans = 0;
	ll l, r;
	vector<pair<ll, ll>> vec;
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld", &l, &r);	
		if (ok) {
			ans += (r - l + 1);
		}
		if (r - l + 1 >= maxn) {
			cout << maxn;
			return 0;
		}
		if (l % maxn > r % maxn) {
			vec.push_back({l % maxn, maxn - 1});
			vec.push_back({0, r % maxn});
		} else {
			vec.push_back({l % maxn, r % maxn});
		}
		//cout << tr.get(0, maxn - 1) << endl;
		//cout << l % maxn << ' ' << r % maxn << endl;
	}
	if (ok) {
		cout << ans;
		return 0;
	}
	ans = 0;
	sort(vec.begin(), vec.end());
	ll cur = -1;
	for (int i = 0; i < vec.size(); i++) {
		 // cout << vec[i].fr << ' ' << vec[i].sc << ' ' << cur << ' ' << ans << endl;
		if (vec[i].sc < cur) continue;
		ans += (vec[i].sc - max(cur + 1, vec[i].fr) + 1);
		cur = max(cur, vec[i].sc);
	}
	cout << ans << endl;
	return 0;
	for (ll i = 1; i <= 50; i++) {
		cout << i << "| (" << (i + i / b) % a << ", " << i % b << ')' << endl;
	}
}
/*
3 3 3
4 4
7 9
17 18
*/

Compilation message (stderr)

strange_device.cpp:25:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
strange_device.cpp: In function 'int main()':
strange_device.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~
strange_device.cpp:26:7: 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:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &l, &r); 
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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