Submission #233403

#	Time	Username	Problem	Language	Result	Execution time	Memory
233403		priyansh5525	Strange Device (APIO19_strange_device)	C++17	100 / 100	623 ms	60016 KiB

strange_device

#include<bits/stdc++.h>
	using namespace std;
	#define ll long long int
	#define pii pair<long long int,long long int>
	#define vi vector<long long int >
	#define vvi vector<vector< long long int>>
	#define MP make_pair
	#define PB push_back 
	#define pb pop_back
	#define PF push_front
	#define pf pop_front
	#define MOD 1000000007

	int main()
	{
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
		ll n,a,b;
		vector<pii> vec;
		cin>>n>>a>>b;
		for(ll i=0;i<n;i++)
		{
			ll x,y;
			cin>>x>>y;
			vec.PB(MP(x,y));
		}
		// solve equation t2 = x*fac+t1
		ll fac = a/__gcd(a,b+1);
		fac*=b;
		if(fac<=0)
			fac=1e18+1;
		ll ans=0;
		vector<pii> ve;
		for(ll i=0;i<n;i++)
		{
			ll x=vec[i].first,y=vec[i].second;
			if(y-x+1>=fac)
			{
				ans=fac;
				break;
			}
			if((x%fac)<=(y%fac))
			{
				ve.PB(MP(x%fac,y%fac));
			}
			else
			{
				ve.PB(MP(x%fac,fac-1));
				ve.PB(MP(0,y%fac));
			}
		}
		if(ans==0)
		{
		sort(ve.begin(),ve.end());
		ll k=ve.size();
		for(ll i=0;i<k;i++)
		{
			ll x=ve[i].first,y=ve[i].second;
			ll j=i+1;
			//cout<<x<<" "<<y<<endl;
			while(j<k && ve[j].first<=(y+1))
			{
				y=max(ve[j].second,y);
				//cout<<x<<" "<<y<<endl;
				j++;
			}
			ans+= (y-x+1);
			i=j-1;
		}
	 	}
	 	cout<<ans<<"\n";
		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