oj.uz

Submission #171153

# Submission time Handle Problem Language Result Execution time Memory
171153 2019-12-27T13:57:45 Z joulej Strange Device (APIO19_strange_device) C++17
35 / 100
 969 ms 35904 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);
	DBG(p);

	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;
		}

		DBG(bal);
		if(bal > 0 && j < len(events)) {
			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 13 ms 1400 KB Output is correct
3 Correct 9 ms 1400 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 0 ms 420 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 1 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 9 ms 1400 KB Output is correct
17 Correct 86 ms 5608 KB Output is correct
18 Runtime error 3 ms 504 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 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Runtime error 7 ms 632 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 504 KB Output is correct
3 Correct 3 ms 508 KB Output is correct
4 Correct 1 ms 400 KB Output is correct
5 Correct 542 ms 33436 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 921 ms 33384 KB Output is correct
3 Correct 787 ms 33472 KB Output is correct
4 Correct 813 ms 33396 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 921 ms 33384 KB Output is correct
3 Correct 787 ms 33472 KB Output is correct
4 Correct 813 ms 33396 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 797 ms 33400 KB Output is correct
7 Correct 771 ms 35320 KB Output is correct
8 Correct 747 ms 35728 KB Output is correct
9 Correct 862 ms 35696 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 921 ms 33384 KB Output is correct
3 Correct 787 ms 33472 KB Output is correct
4 Correct 813 ms 33396 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 74 ms 6216 KB Output is correct
7 Correct 77 ms 6248 KB Output is correct
8 Correct 77 ms 6352 KB Output is correct
9 Correct 74 ms 6244 KB Output is correct
10 Correct 73 ms 6248 KB Output is correct
11 Correct 76 ms 6248 KB Output is correct
12 Correct 73 ms 6220 KB Output is correct
13 Correct 81 ms 6248 KB Output is correct
14 Correct 73 ms 6248 KB Output is correct
15 Correct 84 ms 6248 KB Output is correct
16 Correct 83 ms 6248 KB Output is correct
17 Correct 76 ms 6248 KB Output is correct
18 Correct 767 ms 35720 KB Output is correct
19 Correct 726 ms 35692 KB Output is correct
20 Correct 891 ms 35632 KB Output is correct
21 Correct 86 ms 6888 KB Output is correct
22 Correct 70 ms 6840 KB Output is correct
23 Correct 226 ms 18872 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 82 ms 7148 KB Output is correct
3 Correct 84 ms 7272 KB Output is correct
4 Correct 969 ms 35764 KB Output is correct
5 Correct 83 ms 7116 KB Output is correct
6 Correct 84 ms 7144 KB Output is correct
7 Correct 82 ms 7144 KB Output is correct
8 Correct 86 ms 7144 KB Output is correct
9 Correct 81 ms 7144 KB Output is correct
10 Correct 86 ms 7164 KB Output is correct
11 Correct 82 ms 7180 KB Output is correct
12 Correct 74 ms 7144 KB Output is correct
13 Correct 87 ms 7148 KB Output is correct
14 Correct 869 ms 35752 KB Output is correct
15 Correct 87 ms 7144 KB Output is correct
16 Correct 717 ms 35776 KB Output is correct
17 Correct 751 ms 35904 KB Output is correct
18 Runtime error 3 ms 508 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 13 ms 1400 KB Output is correct
3 Correct 9 ms 1400 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 0 ms 420 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 1 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 9 ms 1400 KB Output is correct
17 Correct 86 ms 5608 KB Output is correct
18 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)