oj.uz

Submission #732830

# Submission time Handle Problem Language Result Execution time Memory
732830 2023-04-29T10:29:42 Z Magikarp4000 Strange Device (APIO19_strange_device) C++17
35 / 100
 517 ms 18140 KB 
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 2e18;

ll n,a,b;
vector<PLL> v;

ll gcd(ll a, ll b) {
    return (b == 0) ? a : gcd(b,a%b);
}

int main() {
    OPTM;
    cin >> n >> a >> b;
    ll prod = a*b;
    ll p = 1;
    if (a != 0 && prod/a != b) p = LLINF;
    else p = a*b/gcd(a,b+1);
    FOR(i,0,n) {
        ll l,r; cin >> l >> r;
        ll c = l%p, d = r%p;
        if (r-l+1 >= p) v.PB({0,p-1});
        else if (d >= c) v.PB({c,d});
        else {
            v.PB({c,p-1});
            v.PB({0,d});
        }
    }
    ll res = 0;
    sort(ALL(v));
    ll vn = v.size();
    ll s = v[0].F, e = v[0].S;
    FOR(i,1,vn) {
        if (v[i].F <= e) e = max(e,v[i].S);
        else {
            res += e-s+1;
            s = v[i].F;
            e = v[i].S;
        }
    }
    res += e-s+1;
    cout << res;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 600 KB Output is correct
3 Correct 5 ms 600 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 612 KB Output is correct
17 Correct 44 ms 2460 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 303 ms 16848 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 387 ms 16920 KB Output is correct
3 Correct 408 ms 16748 KB Output is correct
4 Correct 396 ms 17780 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 387 ms 16920 KB Output is correct
3 Correct 408 ms 16748 KB Output is correct
4 Correct 396 ms 17780 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 415 ms 17628 KB Output is correct
7 Correct 395 ms 17968 KB Output is correct
8 Correct 383 ms 17728 KB Output is correct
9 Correct 517 ms 17968 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 387 ms 16920 KB Output is correct
3 Correct 408 ms 16748 KB Output is correct
4 Correct 396 ms 17780 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 50 ms 3620 KB Output is correct
7 Correct 45 ms 4148 KB Output is correct
8 Correct 39 ms 4060 KB Output is correct
9 Correct 53 ms 4068 KB Output is correct
10 Correct 44 ms 4128 KB Output is correct
11 Correct 47 ms 4164 KB Output is correct
12 Correct 43 ms 4164 KB Output is correct
13 Correct 44 ms 4160 KB Output is correct
14 Correct 39 ms 4048 KB Output is correct
15 Correct 45 ms 4104 KB Output is correct
16 Correct 50 ms 4112 KB Output is correct
17 Correct 53 ms 3588 KB Output is correct
18 Correct 414 ms 17852 KB Output is correct
19 Correct 474 ms 17908 KB Output is correct
20 Correct 504 ms 18028 KB Output is correct
21 Correct 56 ms 4088 KB Output is correct
22 Correct 47 ms 3564 KB Output is correct
23 Correct 142 ms 9832 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 51 ms 2396 KB Output is correct
3 Correct 50 ms 2456 KB Output is correct
4 Correct 479 ms 16840 KB Output is correct
5 Correct 46 ms 3680 KB Output is correct
6 Correct 52 ms 3572 KB Output is correct
7 Correct 47 ms 3680 KB Output is correct
8 Correct 61 ms 3660 KB Output is correct
9 Correct 49 ms 3736 KB Output is correct
10 Correct 51 ms 3580 KB Output is correct
11 Correct 49 ms 3708 KB Output is correct
12 Correct 42 ms 3564 KB Output is correct
13 Correct 49 ms 3608 KB Output is correct
14 Correct 452 ms 18104 KB Output is correct
15 Correct 47 ms 3588 KB Output is correct
16 Correct 387 ms 18140 KB Output is correct
17 Correct 401 ms 18080 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 600 KB Output is correct
3 Correct 5 ms 600 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 4 ms 612 KB Output is correct
17 Correct 44 ms 2460 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -