oj.uz

Submission #171146

# Submission time Handle Problem Language Result Execution time Memory
171146 2019-12-27T13:50:24 Z joulej Strange Device (APIO19_strange_device) C++17
35 / 100
 1010 ms 69292 KB 
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <sstream>
#include <bitset>
#include <cassert>
#include <fstream>
#include <queue>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
	#define DBG(X) cout << #X << "=" << (X) << '\n';
	#define SAY(X) cout << (X) << '\n';
#else
	#define DBG(X)
	#define SAY(X)
#endif
 
using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INT_INF = (int)(2e9);
const ll  LL_INF  = (ll)(2e18);

const int NIL = -1;
static mt19937 _g(time(nullptr));

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for(auto el: v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for(auto& elem: ret) cin >> elem; return ret; }

ll GCD(ll x, ll y) {
	return (x == 0 ? y : GCD(y % x, x));
}

ll calc_period(ll A, ll B) {
	ll k = (A / GCD(A, B + 1));

	return k * B;
}

vector<pll> events;

void add(ll L, ll R) {
	assert(L <= R);

	events.emplace_back(L, +1);
	events.emplace_back(R + 1, -1);
}

void solve() {
	int n = fetch<int>();
	ll A = fetch<ll>();
	ll B = fetch<ll>();
	ll p = calc_period(A, B);

	for(int i = 0; i < n; ++i) {
		ll L = fetch<ll>();
		ll R = fetch<ll>();

		ll sz = R - L + 1;
		if(sz >= p) {
			add(0, p - 1);
		} else {
			L %= p;
			R %= p;

			if(L <= R) {
				add(L, R);
			} else {
				add(0, R);
				add(L, p - 1);
			}
		}
	}

	sort(events.begin(), events.end());
	ll answ = 0;
	ll bal = 0;

	for(int i = 0; i < len(events); ) {
		DBG(i);
		int j = i;
		while(j < len(events) && events[j].first == events[i].first) {
			bal += events[j++].second;
		}

		if(bal > 0) {
			answ += events[j].first - events[i].first;
		}

		i = j;
	}

	cout << answ << '\n';
}

int main() {
	fast_io();
	solve();

	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 10 ms 1400 KB Output is correct
3 Correct 10 ms 1432 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 416 KB Output is correct
7 Correct 1 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 1 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 10 ms 1400 KB Output is correct
17 Correct 87 ms 5476 KB Output is correct
18 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 672 ms 57244 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 756 ms 33472 KB Output is correct
3 Correct 879 ms 69060 KB Output is correct
4 Correct 826 ms 69188 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 756 ms 33472 KB Output is correct
3 Correct 879 ms 69060 KB Output is correct
4 Correct 826 ms 69188 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 761 ms 69116 KB Output is correct
7 Correct 751 ms 69032 KB Output is correct
8 Correct 814 ms 69116 KB Output is correct
9 Correct 978 ms 69164 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 756 ms 33472 KB Output is correct
3 Correct 879 ms 69060 KB Output is correct
4 Correct 826 ms 69188 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 78 ms 7360 KB Output is correct
7 Correct 84 ms 7392 KB Output is correct
8 Correct 119 ms 7420 KB Output is correct
9 Correct 77 ms 7272 KB Output is correct
10 Correct 73 ms 7388 KB Output is correct
11 Correct 78 ms 7392 KB Output is correct
12 Correct 72 ms 7276 KB Output is correct
13 Correct 84 ms 7364 KB Output is correct
14 Correct 75 ms 7364 KB Output is correct
15 Correct 89 ms 7408 KB Output is correct
16 Correct 84 ms 7272 KB Output is correct
17 Correct 76 ms 7540 KB Output is correct
18 Correct 789 ms 69116 KB Output is correct
19 Correct 813 ms 68984 KB Output is correct
20 Correct 909 ms 69040 KB Output is correct
21 Correct 92 ms 7276 KB Output is correct
22 Correct 75 ms 7428 KB Output is correct
23 Correct 231 ms 26784 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 376 KB Output is correct
2 Correct 85 ms 7376 KB Output is correct
3 Correct 90 ms 7364 KB Output is correct
4 Correct 1010 ms 68972 KB Output is correct
5 Correct 91 ms 7472 KB Output is correct
6 Correct 87 ms 7320 KB Output is correct
7 Correct 86 ms 7436 KB Output is correct
8 Correct 90 ms 7308 KB Output is correct
9 Correct 82 ms 7348 KB Output is correct
10 Correct 91 ms 7376 KB Output is correct
11 Correct 83 ms 7524 KB Output is correct
12 Correct 75 ms 7276 KB Output is correct
13 Correct 92 ms 7368 KB Output is correct
14 Correct 923 ms 68996 KB Output is correct
15 Correct 92 ms 7360 KB Output is correct
16 Correct 760 ms 69292 KB Output is correct
17 Correct 770 ms 69160 KB Output is correct
18 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 10 ms 1400 KB Output is correct
3 Correct 10 ms 1432 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 416 KB Output is correct
7 Correct 1 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 1 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 10 ms 1400 KB Output is correct
17 Correct 87 ms 5476 KB Output is correct
18 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)