Submission #374766

#	Time	Username	Problem	Language	Result	Execution time	Memory
374766		AriaH	Strange Device (APIO19_strange_device)	C++11	100 / 100	611 ms	53556 KiB

strange_device

/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
const ld one = 1.;
const ld eps = 1e-12;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

int n;

ll A, B, L;

vector < pll > vec;

int main()
{
	scanf("%d%lld%lld", &n, &A, &B);
	L = A / __gcd(A, B + 1); /// A | t - t2 + (t - t2) / B -> A | (B + 1) * ((t - t2) / B)
	if(one * L * B - one * inf > eps) L = inf;
	else L *= B;
	for(int i = 1; i <= n; i ++)
	{
		ll l, r;
		scanf("%lld%lld", &l, &r);
		if(r - l > L)
		{
			return !printf("%lld", L);
		}
		r %= L, l %= L;
		if(l <= r)
		{
			vec.push_back(Mp(l, r));
		}
		else
		{
			vec.push_back(Mp(l, L - 1));
			vec.push_back(Mp(0, r));
		}
	}
	sort(all(vec));
	ll tot = 0, right = -1;
	for(auto cu : vec)
	{
		right = max(right, cu.F - 1);
		tot += max(0ll, cu.S - right);
		right = max(cu.S, right);
	}
	printf("%lld", tot);
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

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