Submission #154712

#	Time	Username	Problem	Language	Result	Execution time	Memory
154712		HBK_Wasi	Strange Device (APIO19_strange_device)	C++14	100 / 100	3139 ms	53388 KiB

strange_device

#include<bits/stdc++.h>
#define lli long long int
#define int long long int
#define pii pair<int, int>
 
#ifdef LOCAL
#define debug(a) cout<<#a<<' '<<a<<endl;
#endif
 
#ifndef LOCAL
#define debug(a) ;
#endif
 
using namespace std;
void faster(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie();
	cout.tie();
}
 
 
int lcm(int a, int b)
{
	return (a*b)/__gcd(a,b);
} 
map<pii, bool> q; 
 
int32_t main()
{
	#ifdef LOCAL
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
 
	pii x;
	vector<pii> v;
	int i, n, A, B, l, r, mx;
	cin >> n >> A >> B;
	
	if(0==0)
	{
		int ln;
		mx = B*(A/__gcd(A, B+1));
		if((double)(log10(B)+log10(A)-log10(__gcd(A, B+1))) > 18.0) mx = 1000000000000000009;
		for(i=1;i<=n;i++)
		{
			cin >> l >> r;
			int ln = r-l;
			l = l % (mx);
			if(ln>=mx)
			{
 
				cout<<mx<<endl;
				exit(0);
			}
			if(l+ln >= mx)
			{
				v.push_back(pii(l, mx-1));
				v.push_back(pii(0, l+ln-mx));
			}
			else
			{
				v.push_back(pii(l, l+ln));
			}
		} 
		sort(v.begin(), v.end());
		int sum=0, right=-1;
		for(int i=0;i<v.size();i++)
		{
			if(v[i].first > right) sum += (v[i].second-v[i].first+1), right=v[i].second;
			else if(v[i].second > right) sum += (v[i].second-right), right=v[i].second;
		}
		cout<<sum<<endl;
		exit(0);
	}
	cout<<q.size()<<endl;
	return 0;	
}

Compilation message (stderr)

strange_device.cpp: In function 'int32_t main()':
strange_device.cpp:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++)
               ~^~~~~~~~~
strange_device.cpp:43:7: warning: unused variable 'ln' [-Wunused-variable]
   int ln;
       ^~

• 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