oj.uz

Submission #249894

# Submission time Handle Problem Language Result Execution time Memory
249894 2020-07-16T10:21:49 Z godwind Strange Device (APIO19_strange_device) C++14
10 / 100
 1074 ms 82648 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <functional>
//#include <unordered_map>
 
using namespace std;
 
template<typename T> void uin(T &a, T b) {if (b < a) a = b;}
template<typename T> void uax(T &a, T b) {if (b > a) a = b;}
 
#define int long long
#define double long double
#define left left228
#define right right228
#define mp make_pair
#define all(v) v.begin(), v.end()

const int INF = 1100LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int mult(int a, int b) {
	if (a > INF / b) {
		return INF;
	}
	return min( INF, a * b );
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	int n, A, B;
	cin >> n >> A >> B;
	int MOD = mult(A, B);
	set< pair<int,int> > s;
	map<int,int>bal;
	int ans = 0;
	bool all = 0;
	for (int i = 0; i < n; ++i) {
		int l, r;
		cin >> l >> r;
		if (r - l + 1 >= MOD) {
			all = 1;
		}
		int lm = l % MOD;
		int rm = r % MOD;
		if (lm <= rm) {
			++bal[lm];
			--bal[rm + 1];
		} else {
			++bal[lm];
			--bal[MOD];
			++bal[0];
			--bal[rm + 1];
		}
	}
	if (all) {
		cout << MOD << '\n';
		return 0;
	}
	vector< pair<int, int> > v;
	for (auto p : bal) {
		v.emplace_back(p);
	}
	int balance = 0;
	for (int i = 0; i < (int)v.size() - 1; ++i) {
		balance += v[i].second;
		if (balance > 0) {
			ans += v[i + 1].first - v[i].first;
		}
	}
	cout << ans << '\n';
    return 0;
}
 
/*
 
 
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 7 ms 1408 KB Output is correct
3 Correct 7 ms 1408 KB Output is correct
4 Incorrect 0 ms 384 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 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 307 ms 3448 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 820 ms 79564 KB Output is correct
3 Incorrect 912 ms 82644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 820 ms 79564 KB Output is correct
3 Incorrect 912 ms 82644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 820 ms 79564 KB Output is correct
3 Incorrect 912 ms 82644 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 384 KB Output is correct
2 Correct 85 ms 11880 KB Output is correct
3 Correct 88 ms 11884 KB Output is correct
4 Correct 929 ms 82648 KB Output is correct
5 Correct 85 ms 11884 KB Output is correct
6 Correct 89 ms 11892 KB Output is correct
7 Correct 88 ms 11884 KB Output is correct
8 Correct 82 ms 11888 KB Output is correct
9 Correct 87 ms 12012 KB Output is correct
10 Correct 90 ms 11860 KB Output is correct
11 Correct 83 ms 11884 KB Output is correct
12 Correct 92 ms 11920 KB Output is correct
13 Correct 97 ms 11884 KB Output is correct
14 Correct 1074 ms 82220 KB Output is correct
15 Incorrect 83 ms 11500 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 384 KB Output is correct
2 Correct 7 ms 1408 KB Output is correct
3 Correct 7 ms 1408 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -