oj.uz

답안 #410636

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410636 2021-05-23T08:07:59 Z dynam1c 이상한 기계 (APIO19_strange_device) C++17
65 / 100
 955 ms 100304 KB 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(c) (c).begin(),(c).end()

// when you ponder, divide and conquer

#define lo __int128

lo _gcd(lo x, lo y) {
	if (x == 0) return y;
	return _gcd(y % x, x);
}

signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	ll n, a, b;
	cin >> n >> a >> b;
	lo g = _gcd(b+1, (lo) a*b);
	lo m = (lo) a * b / g;
	vector<pair<lo, int>> evs;
	for (int i = 0; i < n; i++) {
		ll xl, xr;
		cin >> xl >> xr;
		xr++;
		lo l = xl % m;
		lo r = xr % m;
		if (r <= l)
			evs.emplace_back(0, -1), evs.emplace_back(r, 1), evs.emplace_back(l, -1), evs.emplace_back(m, 1);
		else
			evs.emplace_back(l, -1), evs.emplace_back(r, 1);
	}
	sort(all(evs));
	ll res = 0;
	lo p = 0;
	int c = 0;
	for (auto [x, t] : evs) {
		if (c == 0) p = x;
		c -= t;
		if (c == 0) res += x-p;
	}
	cout << res << endl;
}
/* --- PSolving ---
 * Simplifying (getting rid of variables, conditions, code logic, etc.)
 * Reframing
 * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
 * Inducing
 * Divide and conquer
 * Working backwards
 * Visual intuition
 * !! Reductions don't have to be specializations, they can be generalizations
 */

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 1484 KB Output is correct
3 Correct 7 ms 1484 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 7 ms 1484 KB Output is correct
17 Correct 80 ms 8536 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 500 ms 73284 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 685 ms 66008 KB Output is correct
3 Correct 760 ms 82608 KB Output is correct
4 Correct 717 ms 82604 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 685 ms 66008 KB Output is correct
3 Correct 760 ms 82608 KB Output is correct
4 Correct 717 ms 82604 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 732 ms 82572 KB Output is correct
7 Correct 698 ms 100304 KB Output is correct
8 Correct 697 ms 100116 KB Output is correct
9 Correct 886 ms 100192 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 685 ms 66008 KB Output is correct
3 Correct 760 ms 82608 KB Output is correct
4 Correct 717 ms 82604 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 65 ms 11248 KB Output is correct
7 Correct 70 ms 11316 KB Output is correct
8 Correct 61 ms 11232 KB Output is correct
9 Correct 67 ms 11320 KB Output is correct
10 Correct 62 ms 11320 KB Output is correct
11 Correct 76 ms 11316 KB Output is correct
12 Correct 63 ms 11312 KB Output is correct
13 Correct 77 ms 11304 KB Output is correct
14 Correct 61 ms 11232 KB Output is correct
15 Correct 83 ms 11284 KB Output is correct
16 Correct 75 ms 11316 KB Output is correct
17 Correct 64 ms 11316 KB Output is correct
18 Correct 701 ms 82528 KB Output is correct
19 Correct 678 ms 67564 KB Output is correct
20 Correct 934 ms 67540 KB Output is correct
21 Correct 92 ms 11316 KB Output is correct
22 Correct 60 ms 11316 KB Output is correct
23 Correct 195 ms 43008 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 77 ms 11316 KB Output is correct
3 Correct 82 ms 11228 KB Output is correct
4 Correct 955 ms 66608 KB Output is correct
5 Correct 76 ms 11320 KB Output is correct
6 Correct 75 ms 11316 KB Output is correct
7 Correct 76 ms 11316 KB Output is correct
8 Correct 81 ms 11264 KB Output is correct
9 Correct 72 ms 11248 KB Output is correct
10 Correct 88 ms 11244 KB Output is correct
11 Correct 83 ms 11240 KB Output is correct
12 Correct 77 ms 11312 KB Output is correct
13 Correct 81 ms 11308 KB Output is correct
14 Correct 896 ms 66652 KB Output is correct
15 Correct 83 ms 11228 KB Output is correct
16 Correct 662 ms 67496 KB Output is correct
17 Correct 695 ms 67564 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 1484 KB Output is correct
3 Correct 7 ms 1484 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 7 ms 1484 KB Output is correct
17 Correct 80 ms 8536 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Incorrect 1 ms 204 KB Output isn't correct
21 Halted 0 ms 0 KB -