Submission #255084

#	Time	Username	Problem	Language	Result	Execution time	Memory
255084		BamiTorabi	Strange Device (APIO19_strange_device)	C++14	100 / 100	553 ms	36600 KiB

strange_device

//Sasayego! Sasayego! Shinzou wo Sasageyo!

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x)  cerr << #x << " = " << x << endl
#define lid (id << 1)
#define rid (lid ^ 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 2e6 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int cnt = 0, len = 0;
pll P[maxN], Q[maxN];

ll gcd(ll a, ll b){
	return (b == 0 ? a : gcd(b, a % b));
}

pll I(pll X, pll Y){
	pll Z;
	Z.first = max(X.first, Y.first);
	Z.second = min(X.second, Y.second);
	if (Z.first > Z.second)
		Z = {-1, -1};
	return Z;
}

pll U(pll X, pll Y){
	pll Z;
	Z.first = min(X.first, Y.first);
	Z.second = max(X.second, Y.second);
	return Z;
}

int main(){
	time_t START = clock();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; ll A, B; scanf("%d%lld%lld", &n, &A, &B);
	ll g = gcd(A, B + 1);
	ll L = (B / g <= INF / A ? A * B / g : INF);
	while (n--){
		ll l, r; scanf("%lld%lld", &l, &r);
		if (L <= (r - l + 1))
			return printf("%lld\n", L), 0;
		if (l >= L)
			l %= L;
		if (r >= L)
			r %= L;
		if (r >= l)
			P[cnt++] = {l, r};
		else{
			P[cnt++] = {l, L - 1};
			P[cnt++] = {0, r};
		}
	}
	sort(P, P + cnt);
	Q[0] = P[0];
	for (int i = 1; i < cnt; i++){
		if (I(Q[len], P[i]).first == -1)
			Q[++len] = P[i];
		else
			Q[len] = U(Q[len], P[i]);
	}
	ll ans = len + 1;
	for (int i = 0; i <= len; i++)
		ans += Q[i].second - Q[i].first;
	printf("%lld\n", ans);
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
	return 0;
}
 

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:57:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; ll A, B; scanf("%d%lld%lld", &n, &A, &B);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:61:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll l, r; scanf("%lld%lld", &l, &r);
            ~~~~~^~~~~~~~~~~~~~~~~~~~

• 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