Submission #209158

#	Time	Username	Problem	Language	Result	Execution time	Memory
209158		mieszko11b	Strange Device (APIO19_strange_device)	C++14	100 / 100	606 ms	53436 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

#define X first
#define Y second

ll INF = ll(1e18) + 7;

int n;
ll A, B, T;
vector<pll> S;

int main() {
	scanf("%d%lld%lld", &n, &A, &B);
	ll d = __gcd(A, B + 1);

	if(A / d <= INF / B)
		T = A / d * B;
	else
		T = INF;
		
	while(n--) {
		ll l, r;
		scanf("%lld%lld", &l, &r);
		if(l / T == r / T)
			S.emplace_back(l % T, r % T);
		else if(l / T == r / T - 1) {
			S.emplace_back(l % T, T - 1);
			S.emplace_back(0, r % T);
		} else {
			//~ cout << l << " " << r << endl;
			S.emplace_back(0, T - 1);
		}
	}
	
	sort(S.begin(), S.end());
	
	ll res = 0;
	ll last = -1;
	for(auto s : S) {
		//~ cout << s.X << " " << s.Y << endl;
		if(last < s.X)
			res += s.Y - s.X + 1;
		else if(last < s.Y)
			res += s.Y - last;
		last = max(last, s.Y);
	}
	
	printf("%lld\n", res);
	
	return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:18: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:28: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: 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