oj.uz

Submission #871692

# Submission time Handle Problem Language Result Execution time Memory
871692 2023-11-11T10:21:18 Z serifefedartar Strange Device (APIO19_strange_device) C++17
10 / 100
 703 ms 125556 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 20; 
const ll MAXN = 6 * 1e6;

vector<pair<ll,ll>> v;
vector<ll> cc;
ll calc(ll A, ll B) {
	if (1e18 / A < B)
		return 1e18;
	if (1e18 / B < A)
		return 1e18;
	return A * B;
}

int index(ll k) {
	return upper_bound(cc.begin(), cc.end(), k) - cc.begin();
}
ll cnt[MAXN];

int main() {
	fast
	ll n, A, B;
	cin >> n >> A >> B;

	ll period = calc(A, B);
	for (int i = 1; i <= n; i++) {
		ll l, r;
		cin >> l >> r;
		ll left_mod = l % period;
		ll right_mod = r % period;
		if (r - l + 1 > period - left_mod) {
			v.push_back({left_mod, period - 1});
			v.push_back({0, right_mod});
		} else
			v.push_back({left_mod, right_mod});
	}

	for (auto u : v) {
		cc.push_back(u.f);
		cc.push_back(u.s);
		cc.push_back(u.s+1);
	}
	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end());

	for (auto u : v) {
		cnt[index(u.f)]++;
		cnt[index(u.s + 1)]--;
	}
	for (int i = 1; i < MAXN; i++)
		cnt[i] += cnt[i-1];

	ll ans = 0;
	for (int i = 0; i < cc.size() - 1; i++) {
		if (cnt[i+1]) {
			ans += cc[i+1] - cc[i];
		}
	}
	cout << ans << "\n";
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 0; i < cc.size() - 1; i++) {
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47192 KB Output is correct
2 Correct 23 ms 48208 KB Output is correct
3 Correct 23 ms 48212 KB Output is correct
4 Incorrect 18 ms 47192 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 19 ms 47192 KB Output is correct
2 Correct 18 ms 47276 KB Output is correct
3 Correct 19 ms 47196 KB Output is correct
4 Correct 18 ms 47184 KB Output is correct
5 Correct 19 ms 47268 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47192 KB Output is correct
2 Correct 19 ms 47324 KB Output is correct
3 Correct 20 ms 47432 KB Output is correct
4 Correct 19 ms 47440 KB Output is correct
5 Correct 289 ms 113140 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47196 KB Output is correct
2 Correct 543 ms 125556 KB Output is correct
3 Incorrect 553 ms 125364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47196 KB Output is correct
2 Correct 543 ms 125556 KB Output is correct
3 Incorrect 553 ms 125364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47196 KB Output is correct
2 Correct 543 ms 125556 KB Output is correct
3 Incorrect 553 ms 125364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47196 KB Output is correct
2 Correct 78 ms 56388 KB Output is correct
3 Correct 80 ms 56700 KB Output is correct
4 Correct 703 ms 124960 KB Output is correct
5 Correct 77 ms 55204 KB Output is correct
6 Correct 78 ms 55844 KB Output is correct
7 Correct 76 ms 55184 KB Output is correct
8 Correct 80 ms 55184 KB Output is correct
9 Correct 74 ms 56376 KB Output is correct
10 Correct 79 ms 55108 KB Output is correct
11 Correct 76 ms 55700 KB Output is correct
12 Correct 84 ms 56832 KB Output is correct
13 Correct 82 ms 55064 KB Output is correct
14 Correct 669 ms 125516 KB Output is correct
15 Incorrect 84 ms 56936 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47192 KB Output is correct
2 Correct 23 ms 48208 KB Output is correct
3 Correct 23 ms 48212 KB Output is correct
4 Incorrect 18 ms 47192 KB Output isn't correct
5 Halted 0 ms 0 KB -