oj.uz

Submission #1035164

# Submission time Handle Problem Language Result Execution time Memory
1035164 2024-07-26T05:26:53 Z Halym2007 Strange Device (APIO19_strange_device) C++17
10 / 100
 311 ms 69692 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define sz size()
#define pii pair <ll, ll>
const int N = 1e6 + 5;
#define ll long long
#define pb push_back
vector <pii> v;
ll n, a, b, l[N], r[N];
int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> a >> b;
	__int128 m = a / __gcd (a, b + 1) * b;
	bool tr = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> l[i] >> r[i];
	}
	for (int i = 1; i <= n; ++i) {
		if (r[i] - l[i] + 1 >= m) {
			ll kl = m;
			return cout << kl, 0;
		}
		if (l[i] % m > r[i] % m) {
			v.pb ({l[i] % m, m - 1});
			v.pb ({0, r[i] % m});
		}
		else {
			v.pb ({l[i] % m, r[i] % m});
		}
	}
	sort (v.begin(), v.end());
//	for (auto i : v) {
//		cout << i.ff << " " << i.ss << "\n";
//	}
//	return 0;
	ll l1 = 0, r1 = 0, jogap = 0;
	for (int i = 0; i < (int)v.sz; ++i) {
		if (v[i].ff <= r1) r1 = max (r1, v[i].ss);
		
		else {
			jogap += r1 - l1 + 1;
			l1 = v[i].ff; 
			r1 = v[i].ss;
		}
	}
	jogap += r1 - l1 + 1;
	cout << jogap;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:17:7: warning: unused variable 'tr' [-Wunused-variable]
   17 |  bool tr = 0;
      |       ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 3 ms 1204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 476 KB Output is correct
5 Correct 208 ms 57764 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 284 ms 69692 KB Output is correct
3 Correct 280 ms 69564 KB Output is correct
4 Correct 281 ms 69564 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 284 ms 69692 KB Output is correct
3 Correct 280 ms 69564 KB Output is correct
4 Correct 281 ms 69564 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 280 ms 69568 KB Output is correct
7 Correct 311 ms 69572 KB Output is correct
8 Correct 281 ms 69572 KB Output is correct
9 Incorrect 299 ms 69568 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 284 ms 69692 KB Output is correct
3 Correct 280 ms 69564 KB Output is correct
4 Correct 281 ms 69564 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 27 ms 7896 KB Output is correct
7 Correct 29 ms 7900 KB Output is correct
8 Correct 27 ms 7888 KB Output is correct
9 Correct 29 ms 7896 KB Output is correct
10 Correct 27 ms 7888 KB Output is correct
11 Correct 29 ms 7884 KB Output is correct
12 Correct 28 ms 7888 KB Output is correct
13 Incorrect 39 ms 8152 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 32 ms 7816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 3 ms 1204 KB Output isn't correct
3 Halted 0 ms 0 KB -