Submission #126587

#	Time	Username	Problem	Language	Result	Execution time	Memory
126587		roseanne_pcy	Strange Device (APIO19_strange_device)	C++14	35 / 100	911 ms	49196 KiB

strange_device

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e6+5;
ll L[maxn], R[maxn];

vector< pair<ll, int> > sw;

int main()
{
	int n;
	ll A, B;
	scanf("%d %lld %lld", &n, &A, &B);
	ll k = A/__gcd(A, B+1);
	bool over = false;
	if(k*B/B != k) over = true;
	ll len = 0;
	for(int i = 1; i<= n; i++)
	{
		scanf("%lld %lld", &L[i], &R[i]);
		len += (R[i]-L[i]+1);
	}
	if(over)
	{
		printf("%lld\n", len);
		return 0;
	}
	for(int i = 1; i<= n; i++)
	{
		ll tmp = R[i]-L[i]+1;
		if(tmp>= k*B)
		{
			printf("%lld\n", k*B);
			return 0;
		}
		ll m1 = L[i]%(k*B);
		ll m2 = R[i]%(k*B);
		if(m1<= m2) 
		{
			sw.pb({m1, 1});
			sw.pb({m2+1, -1});
		}
		else
		{
			sw.pb({m1, 1});
			sw.pb({k*B, -1});
			sw.pb({0, 1});
			sw.pb({m2+1, -1});
		}
	}
	sort(sw.begin(), sw.end());
	ll ans = 0;
	int run = 0;
	for(int i = 0; i+1< (int) sw.size(); i++)
	{
		run += sw[i].Y;
		if(run> 0)
		{
			ans += sw[i+1].X-sw[i].X;
		}
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:20: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:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &L[i], &R[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30