Submission #564143

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
564143	2022-05-18T15:32:56 Z	ngpin04	Strange Device (APIO19_strange_device)	C++14	15 / 100	598 ms	33468 KB

strange_device

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

long long lcm(long long a, long long b) {
	long long res = a / __gcd(a, b);
	if (res > 2 * ooo / b)
		return 2 * ooo;
	return res * b;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	long long n, A, B;
	cin >> n >> A >> B;
	long long x = __gcd(A, B + 1);
	long long y = __gcd(A, B);
	A /= x;
	if (A > 2 * ooo / y)
		A = 2 * ooo;	
	else
		A *= y;

	long long len = lcm(A, B);
	assert(len < 2 * ooo);

	vector <pair <long long, int>> events;

	for (int i = 1; i <= n; i++) {
		long long l, r;
		cin >> l >> r;
		if (r - l + 1 >= len) 		
			return cout << len, 0;

		events.push_back(mp(l % len, 1));
		events.push_back(mp(r % len + 1, -1));
		if (l % len > r % len) {
			events.push_back(mp(0, 1));
			events.push_back(mp(len, -1));
		}	
	}
	sort(ALL(events));

	long long ans = 0;
	long long pre = 0;
	int cnt = 0;
	for (pair <long long, int> pir : events) {
		if (cnt > 0) 
			ans += pir.fi - pre;
		// cerr << pre << " " << pir.fi << "\n";
		cnt += pir.se;
		pre = pir.fi;
	}
	cout << ans;
	return 0;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	4 ms	856 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Runtime error	1 ms	468 KB	Execution killed with signal 6
6	Halted	0 ms	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	321 ms	33220 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	475 ms	33244 KB	Output is correct
3	Correct	496 ms	33212 KB	Output is correct
4	Correct	459 ms	33248 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	475 ms	33244 KB	Output is correct
3	Correct	496 ms	33212 KB	Output is correct
4	Correct	459 ms	33248 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	480 ms	33164 KB	Output is correct
7	Correct	457 ms	33232 KB	Output is correct
8	Correct	464 ms	33200 KB	Output is correct
9	Correct	550 ms	33208 KB	Output is correct

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	475 ms	33244 KB	Output is correct
3	Correct	496 ms	33212 KB	Output is correct
4	Correct	459 ms	33248 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	47 ms	4556 KB	Output is correct
7	Correct	48 ms	4548 KB	Output is correct
8	Correct	48 ms	4552 KB	Output is correct
9	Correct	47 ms	4456 KB	Output is correct
10	Correct	44 ms	4544 KB	Output is correct
11	Incorrect	46 ms	4480 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	50 ms	4540 KB	Output is correct
3	Correct	57 ms	4548 KB	Output is correct
4	Correct	598 ms	33232 KB	Output is correct
5	Correct	50 ms	4556 KB	Output is correct
6	Correct	54 ms	4468 KB	Output is correct
7	Correct	50 ms	4512 KB	Output is correct
8	Correct	55 ms	4580 KB	Output is correct
9	Correct	48 ms	4556 KB	Output is correct
10	Correct	54 ms	4556 KB	Output is correct
11	Correct	51 ms	4476 KB	Output is correct
12	Correct	44 ms	4548 KB	Output is correct
13	Correct	55 ms	4512 KB	Output is correct
14	Correct	558 ms	33468 KB	Output is correct
15	Correct	56 ms	4588 KB	Output is correct
16	Correct	447 ms	33284 KB	Output is correct
17	Correct	472 ms	33268 KB	Output is correct
18	Runtime error	1 ms	468 KB	Execution killed with signal 6
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	4 ms	856 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Submission #564143

Compilation message