Submission #383380

#	Time	Username	Problem	Language	Result	Execution time	Memory
383380		Saynaa	Strange Device (APIO19_strange_device)	C++17	100 / 100	525 ms	29776 KiB

strange_device

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 10;
const ll ziad = LLONG_MAX/2;
int n;
ll a, b;
vector< pair<ll, ll> >vec;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	cin >> a >> b;
	ll x = __gcd(a, b + 1);
	x = a/x;
	if( x <= ziad/b) x *= b;
	else x = ziad;
	for(int i = 0; i < n; i ++){
		ll l, r;
		cin >> l >> r;
		if(r - l + 1 >= x){
			cout << x << endl;
			return 0;
		}
		else{
			l %= x, r %= x;
			if( l <= r)
				vec.push_back({l, r});
			else
				vec.push_back({l, x - 1}), vec.push_back({0, r});
		}
	}
	sort(vec.begin(), vec.end());
	ll mx = LLONG_MIN, ans = 0;
	for(int i = 0; i < vec.size(); i ++){
		ll l = vec[i].first, r = vec[i].second;
		if( l > mx) ans += r - l + 1;
		else if( r >= mx) ans += r - mx;
		mx = max(mx, r);
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i = 0; i < vec.size(); i ++){
      |                 ~~^~~~~~~~~~~~

• 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