Submission #255059

#	Time	Username	Problem	Language	Result	Execution time	Memory
255059		BamiTorabi	Strange Device (APIO19_strange_device)	C++14	5 / 100	610 ms	37496 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];

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

pll U(pll X, pll Y){
	if (X > Y)
		swap(X, Y);
	pll Z;
	Z.first = X.first;
	Z.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);
	while (n--){
		ll l, r; scanf("%lld%lld", &l, &r);
		if (A <= (r - l + 1) / B)
			return printf("%lld\n", A * B), 0;
		if (A <= l / B)
			l %= A * B;
		if (A <= r / B)
			r %= A * B;
		if (r >= l)
			P[cnt++] = {l, r};
		else{
			P[cnt++] = {l, A * B - 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:59: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: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30