Submission #335155

#	Time	Username	Problem	Language	Result	Execution time	Memory
335155		nicholask	Strange Device (APIO19_strange_device)	C++14	100 / 100	1574 ms	34704 KiB

strange_device

#include <bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int a,int b){
	while (b) b^=a^=b^=a%=b;
	return a;
}
signed main(){
	int n,a,b;
	cin>>n>>a>>b;
	a/=gcd(a,b+1);
	pair <int,int> p[n];
	for (int i=0; i<n; i++) cin>>p[i].first>>p[i].second;
	int lim=(a<=(1e18+5)/b?a*b:1e18+5);
	vector <pair <int,int> > v;
	for (int i=0; i<n; i++){
		if (p[i].second-p[i].first+1>=lim){
			cout<<lim;
			return 0;
		}
		p[i].first%=lim;
		p[i].second%=lim;
		if (p[i].first<=p[i].second) v.push_back({p[i].first,p[i].second});
		else {
			v.push_back({p[i].first,lim-1});
			v.push_back({0,p[i].second});
		}
	}
	sort(v.begin(),v.end());
	int ans=0,lb=v[0].first,rb=v[0].second;
	for (int i=1; i<v.size(); i++){
		if (v[i].first>rb){
			ans+=rb-lb+1;
			rb=v[i].second;
			lb=v[i].first;
		} else rb=max(rb,v[i].second);
	}
	cout<<ans+rb-lb+1;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:31:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (int i=1; i<v.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