oj.uz

Submission #249891

# Submission time Handle Problem Language Result Execution time Memory
249891 2020-07-16T10:16:23 Z godwind Strange Device (APIO19_strange_device) C++14
10 / 100
 955 ms 81044 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 + 1) {
		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 9 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 1 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 308 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 314 ms 1536 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 823 ms 79708 KB Output is correct
3 Incorrect 893 ms 80768 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 823 ms 79708 KB Output is correct
3 Incorrect 893 ms 80768 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 823 ms 79708 KB Output is correct
3 Incorrect 893 ms 80768 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 87 ms 10092 KB Output is correct
3 Correct 81 ms 10092 KB Output is correct
4 Correct 888 ms 81044 KB Output is correct
5 Correct 86 ms 10092 KB Output is correct
6 Correct 97 ms 10092 KB Output is correct
7 Correct 86 ms 10092 KB Output is correct
8 Correct 84 ms 10092 KB Output is correct
9 Correct 94 ms 10092 KB Output is correct
10 Correct 77 ms 10096 KB Output is correct
11 Correct 80 ms 10092 KB Output is correct
12 Correct 81 ms 10092 KB Output is correct
13 Correct 87 ms 10096 KB Output is correct
14 Correct 955 ms 80576 KB Output is correct
15 Incorrect 87 ms 9964 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 9 ms 1408 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -