oj.uz

Submission #782603

# Submission time Handle Problem Language Result Execution time Memory
782603 2023-07-14T06:22:25 Z christinelynn Strange Device (APIO19_strange_device) C++17
65 / 100
 369 ms 17556 KB 
# include <bits/stdc++.h>
# define int long long
# define vi vector<int>
# define pb push_back
# define pii pair<int, int>
# define fi first
# define se second
# define endl '\n'
# define jess ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int n, a, b;

void solve() {
    cin >> n >> a >> b;
    __int128_t t=(__int128_t)a*b;
    __int128_t cycle=t / (__int128_t)__gcd(a, b+1);
    vector<pii> v;
    for(int i=1; i<=n; i++) {
        int l, r;
        cin >> l >> r;
        if((r-l+1) >= cycle) {
            cout << r-l+1 << endl;
            return;
        }
        l%=cycle;
        r%=cycle;
        if(r < l) {
            v.pb({l, cycle-1});
            v.pb({0, r});
        } else {
            v.pb({l, r});
        }
    }
    sort(v.begin(), v.end());
    bool st=1;
    int l=0, r=1, ans=0;
    // for(pii i : v) cout << "l r " << i.fi << " " << i.se << endl;
    for(auto i : v) {
        if(st) {
            l=i.fi, r=i.se;
            st=0;
            continue;
        }
        if(i.fi>=l && i.fi<=r) {
            r=max(r, i.se);
        } else {
            ans+=(r-l+1);
            l=i.fi, r=i.se;
        }
    }
    ans+=(r-l+1);
    cout << ans << endl;
}
 
signed main() {
    jess;
    solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 932 KB Output is correct
3 Correct 4 ms 856 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 316 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 324 KB Output is correct
16 Correct 5 ms 852 KB Output is correct
17 Correct 36 ms 2900 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 368 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 207 ms 16892 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 314 ms 16892 KB Output is correct
3 Correct 304 ms 17480 KB Output is correct
4 Correct 314 ms 17228 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 314 ms 16892 KB Output is correct
3 Correct 304 ms 17480 KB Output is correct
4 Correct 314 ms 17228 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 315 ms 17556 KB Output is correct
7 Correct 323 ms 17320 KB Output is correct
8 Correct 310 ms 17280 KB Output is correct
9 Correct 369 ms 16888 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 314 ms 16892 KB Output is correct
3 Correct 304 ms 17480 KB Output is correct
4 Correct 314 ms 17228 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 30 ms 2524 KB Output is correct
7 Correct 31 ms 2560 KB Output is correct
8 Correct 32 ms 2464 KB Output is correct
9 Correct 36 ms 2484 KB Output is correct
10 Correct 38 ms 2440 KB Output is correct
11 Correct 30 ms 2480 KB Output is correct
12 Correct 29 ms 2536 KB Output is correct
13 Correct 36 ms 2500 KB Output is correct
14 Correct 29 ms 2444 KB Output is correct
15 Correct 34 ms 2416 KB Output is correct
16 Correct 36 ms 2452 KB Output is correct
17 Correct 37 ms 2544 KB Output is correct
18 Correct 322 ms 16904 KB Output is correct
19 Correct 306 ms 16812 KB Output is correct
20 Correct 315 ms 16780 KB Output is correct
21 Correct 31 ms 2512 KB Output is correct
22 Correct 28 ms 2512 KB Output is correct
23 Correct 89 ms 8568 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 31 ms 2512 KB Output is correct
3 Correct 31 ms 2512 KB Output is correct
4 Correct 355 ms 16812 KB Output is correct
5 Correct 31 ms 2512 KB Output is correct
6 Correct 31 ms 2512 KB Output is correct
7 Correct 31 ms 2472 KB Output is correct
8 Correct 32 ms 2464 KB Output is correct
9 Correct 32 ms 2512 KB Output is correct
10 Correct 31 ms 2484 KB Output is correct
11 Correct 31 ms 2512 KB Output is correct
12 Correct 28 ms 2488 KB Output is correct
13 Correct 31 ms 2436 KB Output is correct
14 Correct 318 ms 16868 KB Output is correct
15 Correct 36 ms 2484 KB Output is correct
16 Correct 298 ms 16764 KB Output is correct
17 Correct 296 ms 16904 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 932 KB Output is correct
3 Correct 4 ms 856 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 316 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 324 KB Output is correct
16 Correct 5 ms 852 KB Output is correct
17 Correct 36 ms 2900 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Incorrect 0 ms 320 KB Output isn't correct
21 Halted 0 ms 0 KB -