oj.uz

Submission #252822

# Submission time Handle Problem Language Result Execution time Memory
252822 2020-07-26T10:17:16 Z Erkhemkhuu Strange Device (APIO19_strange_device) C++17
15 / 100
 218 ms 3704 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
const ll N = 100005;
const ll lim = 1e18;
pair <ll, ll> arr[N];
int main() {
    ll n, a, b, t, m, i, sz, l, r, ans;
    cin >> n >> a >> b;
    t = a / (__gcd(a, b + 1));
    m = ((t > lim / b) ? (lim + 1) : (t * b));
    sz = 0;
    while(n--) {
        cin >> l >> r;
        if(r - l + 1 >= m) {
            cout << m << "\n";
            return 0;
        }
        l %= m;
        r %= m;
        if(l <= r) {
            arr[++sz].F = l;
            arr[sz].S = r;
        }
        else {
            arr[++sz].F = l;
            arr[sz].S = m - 1;
            arr[++sz].F = 0;
            arr[sz].S = r;
        }
    }
    sort(arr + 1, arr + sz + 1);
    ans = 0; r = -1;
    for(i = 1; i <= sz; i++) {
        r = max(r, arr[i].F - 1);
        ans += max(0ll, arr[i].S - r);
        r = max(r, arr[i].S);
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 21 ms 424 KB Output is correct
3 Correct 21 ms 512 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 21 ms 512 KB Output is correct
17 Correct 213 ms 1912 KB Output is correct
18 Correct 0 ms 256 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Runtime error 151 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Runtime error 209 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Runtime error 209 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Runtime error 209 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 218 ms 1824 KB Output is correct
3 Correct 209 ms 1912 KB Output is correct
4 Runtime error 204 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 21 ms 424 KB Output is correct
3 Correct 21 ms 512 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 21 ms 512 KB Output is correct
17 Correct 213 ms 1912 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 0 ms 256 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 0 ms 256 KB Output is correct
23 Correct 1 ms 256 KB Output is correct
24 Correct 0 ms 256 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Runtime error 151 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)