oj.uz

Submission #871705

# Submission time Handle Problem Language Result Execution time Memory
871705 2023-11-11T10:49:58 Z serifefedartar Strange Device (APIO19_strange_device) C++17
10 / 100
 670 ms 88876 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 + 50;

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 18 ms 47192 KB Output is correct
2 Correct 23 ms 47696 KB Output is correct
3 Correct 24 ms 47700 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 47196 KB Output is correct
2 Correct 18 ms 47192 KB Output is correct
3 Correct 18 ms 47196 KB Output is correct
4 Correct 18 ms 47272 KB Output is correct
5 Correct 19 ms 47556 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47196 KB Output is correct
2 Correct 19 ms 47404 KB Output is correct
3 Correct 19 ms 47300 KB Output is correct
4 Correct 19 ms 47320 KB Output is correct
5 Correct 264 ms 87844 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 518 ms 87016 KB Output is correct
3 Incorrect 513 ms 88876 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 518 ms 87016 KB Output is correct
3 Incorrect 513 ms 88876 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 518 ms 87016 KB Output is correct
3 Incorrect 513 ms 88876 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 51924 KB Output is correct
3 Correct 83 ms 53036 KB Output is correct
4 Correct 670 ms 87584 KB Output is correct
5 Correct 80 ms 53164 KB Output is correct
6 Correct 75 ms 52008 KB Output is correct
7 Correct 81 ms 52952 KB Output is correct
8 Correct 78 ms 51776 KB Output is correct
9 Correct 74 ms 51240 KB Output is correct
10 Correct 79 ms 52032 KB Output is correct
11 Correct 75 ms 51528 KB Output is correct
12 Correct 72 ms 52616 KB Output is correct
13 Correct 79 ms 53064 KB Output is correct
14 Correct 628 ms 88356 KB Output is correct
15 Incorrect 91 ms 52800 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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