# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
531653 | 2022-03-01T08:02:47 Z | 79brue | Strange Device (APIO19_strange_device) | C++14 | 485 ms | 69672 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n; ll a, b; ll l[1000002], r[1000002]; int main(){ scanf("%d %lld %lld", &n, &a, &b); for(int i=1; i<=n; i++) scanf("%lld %lld", &l[i], &r[i]); if(1000000000000000000LL / a + 1 <= b){ ll ans = 0; for(int i=1; i<=n; i++) ans += r[i] - l[i] + 1; printf("%lld", ans); return 0; } if(b==1) a=(a%2==0 ? a/2 : a); else if(b%a==1) a=b; else a = a*b; for(int i=1; i<=n; i++){ if(r[i] - l[i] >= a-1){ printf("%lld", a); return 0; } } vector<pair<ll, ll> > vec; for(int i=1; i<=n; i++){ if(l[i]%a <= r[i]%a) vec.push_back(make_pair(l[i]%a, r[i]%a)); else{ vec.push_back(make_pair(0, r[i]%a)); vec.push_back(make_pair(l[i]%a, a-1)); } } sort(vec.begin(), vec.end()); ll ans = 0; ll rMax = vec[0].second; ll lPnt = vec[0].first; for(int i=0; i<(int)vec.size(); i++){ rMax = max(rMax, vec[i].second); if(i<(int)vec.size()-1 && rMax < vec[i+1].first){ ans += rMax - lPnt + 1; lPnt = vec[i+1].first; } else if(i==(int)vec.size()-1){ ans += rMax - lPnt + 1; } else{ rMax = max(rMax, vec[i].second); } } printf("%lld", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 4 ms | 844 KB | Output is correct |
3 | Correct | 5 ms | 844 KB | Output is correct |
4 | Incorrect | 0 ms | 204 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 306 ms | 32396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 449 ms | 32476 KB | Output is correct |
3 | Correct | 421 ms | 32440 KB | Output is correct |
4 | Correct | 455 ms | 69672 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 449 ms | 32476 KB | Output is correct |
3 | Correct | 421 ms | 32440 KB | Output is correct |
4 | Correct | 455 ms | 69672 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 459 ms | 69632 KB | Output is correct |
7 | Correct | 444 ms | 69652 KB | Output is correct |
8 | Incorrect | 466 ms | 69652 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 449 ms | 32476 KB | Output is correct |
3 | Correct | 421 ms | 32440 KB | Output is correct |
4 | Correct | 455 ms | 69672 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 43 ms | 7720 KB | Output is correct |
7 | Correct | 47 ms | 7736 KB | Output is correct |
8 | Correct | 45 ms | 7724 KB | Output is correct |
9 | Correct | 48 ms | 7664 KB | Output is correct |
10 | Correct | 45 ms | 7836 KB | Output is correct |
11 | Correct | 47 ms | 7700 KB | Output is correct |
12 | Correct | 45 ms | 7740 KB | Output is correct |
13 | Correct | 45 ms | 7736 KB | Output is correct |
14 | Incorrect | 47 ms | 7736 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 46 ms | 4024 KB | Output is correct |
3 | Correct | 44 ms | 3996 KB | Output is correct |
4 | Correct | 485 ms | 32464 KB | Output is correct |
5 | Correct | 46 ms | 4024 KB | Output is correct |
6 | Correct | 48 ms | 4044 KB | Output is correct |
7 | Correct | 46 ms | 4040 KB | Output is correct |
8 | Correct | 44 ms | 3932 KB | Output is correct |
9 | Correct | 44 ms | 4024 KB | Output is correct |
10 | Correct | 45 ms | 3992 KB | Output is correct |
11 | Correct | 46 ms | 4024 KB | Output is correct |
12 | Correct | 39 ms | 4024 KB | Output is correct |
13 | Correct | 45 ms | 3968 KB | Output is correct |
14 | Correct | 462 ms | 32508 KB | Output is correct |
15 | Incorrect | 45 ms | 4024 KB | Output isn't correct |
16 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 4 ms | 844 KB | Output is correct |
3 | Correct | 5 ms | 844 KB | Output is correct |
4 | Incorrect | 0 ms | 204 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |