oj.uz

Submission #448191

# Submission time Handle Problem Language Result Execution time Memory
448191 2021-07-29T08:26:30 Z Vladithur Strange Device (APIO19_strange_device) C++17
10 / 100
 953 ms 66156 KB 
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops")
//#include <x86intrin.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define PI 3.141592653589793L
#define FAST ios::sync_with_stdio(false); cin.tie(NULL);
// Use for file I/O;
#define FIN string _fname = "input"; \
			string _is = _fname + ".in", _os = _fname + ".out"; \
			freopen(_is.c_str(), "r", stdin); \
			freopen(_os.c_str(), "w", stdout);

#define FIN2 freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define RINIT mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

using namespace std;
//using namespace __gnu_pbds;
//typedef gp_hash_table<int, int, hash<int>> ht;

const char nl = '\n';

typedef long long ll;
typedef long double ld;
// typedef unsigned int uint;
typedef unsigned long long ull;

const ll inf = 1e9 + 10;
const ll inf2 = 1e18 + 99LL;
const ld inf3 = 1e17;
const ll mod = 1e9+7, mod2 = 998244353;
const ld eps = 1e-9;
const bool local = false;

//RINIT;
const int logn = 21, maxn = 1000000, maxm = 100000, maxn2 = 3;	

int main() {
	FAST;
	
	int n;
	cin >> n;
	ll ta, tb;
	cin >> ta >> tb;
	//auto g = gcd(ta, tb);
	//ta /= g; tb /= g;
	//cout << ta << ' ' << tb << ' ' << tn << nl;
	__int128 a = ta, b = tb;
	//a /= g;
	//b /= g;
	__int128 tn = a * b;
	
	vector<pair<__int128, ll>> segs;
	while (n--) {
		ll l, r;
		cin >> l >> r;
		
		if (r - l + 1 >= tn) {
			segs.emplace_back(0, 1);
			segs.emplace_back(tn, -1);
		} else {
			l %= tn;
			r %= tn;
			if (l <= r) {
				segs.emplace_back(l, 1);
				segs.emplace_back(r + 1, -1);
			} else {
				segs.emplace_back(0, 1);
				segs.emplace_back(r + 1, -1);
				segs.emplace_back(l, 1);
				segs.emplace_back(tn, -1);
			}
		}
	}
	
	sort(all(segs));
	__int128 ans = 0, ti = 0, px = -1, ct = 0;
	while (ti < gsize(segs)) {
		__int128 tx = segs[ti].first;
		if (ct) ans += tx - px;
		px = tx;
		while (ti < gsize(segs) && segs[ti].first == tx) {
			ct += segs[ti].second;
			ti++;
		}
	}
	
	cout << (ll)ans << nl;
}

// © Benq 
/* stuff you should look for
	* int overflow, array bounds	
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 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 477 ms 66092 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 701 ms 66064 KB Output is correct
3 Incorrect 645 ms 66156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 701 ms 66064 KB Output is correct
3 Incorrect 645 ms 66156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 701 ms 66064 KB Output is correct
3 Incorrect 645 ms 66156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 74 ms 8644 KB Output is correct
3 Correct 79 ms 8820 KB Output is correct
4 Correct 953 ms 66068 KB Output is correct
5 Correct 75 ms 8688 KB Output is correct
6 Correct 75 ms 8672 KB Output is correct
7 Correct 75 ms 8640 KB Output is correct
8 Correct 80 ms 8640 KB Output is correct
9 Correct 77 ms 8612 KB Output is correct
10 Correct 82 ms 8596 KB Output is correct
11 Correct 75 ms 8628 KB Output is correct
12 Correct 64 ms 8592 KB Output is correct
13 Correct 79 ms 8624 KB Output is correct
14 Correct 882 ms 66060 KB Output is correct
15 Incorrect 82 ms 8624 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -