oj.uz

Submission #527006

# Submission time Handle Problem Language Result Execution time Memory
527006 2022-02-16T19:37:51 Z Lobo Strange Device (APIO19_strange_device) C++17
30 / 100
 450 ms 53280 KB 
#include<bits/stdc++.h>
using namespace std;
 
const long long inf = (long long) 2e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
 
#define maxn 
 
void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    int gc = __gcd(a,b+1);
    int q = (b+1)/gc;
    int m;
    if(log2(a) + log2(b) + log2(q) - log2(b) > log2(inf)) m = inf;
    else m = a*b*q/(b+1);
 
    vector<pair<int,int>> lr;
 
    for(int i = 1; i <= n; i++) {
        int l, r; cin >> l >> r;
 
        if(r-l+1 >= m) {
            lr.pb(mp(0,m-1));
        }
        else if(l/m != r/m) {
            //terminam em cantos diferentes
            l%= m;
            r%= m;
            //colocar l,m-1 e 0,r
            lr.pb(mp(l,m-1));
            lr.pb(mp(0,r));
        }
        else {
            l%= m;
            r%= m;
            lr.pb(mp(l,r));
        }
    }
 
    sort(all(lr));
 
    int l = 0;
    int r = -1;
    int ans = 0;
    for(auto x : lr) {
        int l1 = x.fr;
        int r1 = x.sc;

 
        if(l1 > r) {
            //conta o lr anterior e comeca um novo
            ans+= r-l+1;
            l = l1;
            r = r1;
        }
        r = max(r,r1);
    }
 
    ans+= r-l+1;
    cout << ans << endl;
 
 
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);
 
    int tt = 1;
    // cin >> tt;
    while(tt--) solve();
 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 5 ms 592 KB Output is correct
3 Correct 5 ms 592 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 4 ms 972 KB Output is correct
17 Correct 52 ms 5676 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 327 ms 16848 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 375 ms 16808 KB Output is correct
3 Correct 376 ms 16780 KB Output is correct
4 Correct 414 ms 53228 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 375 ms 16808 KB Output is correct
3 Correct 376 ms 16780 KB Output is correct
4 Correct 414 ms 53228 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 394 ms 53168 KB Output is correct
7 Correct 407 ms 53276 KB Output is correct
8 Correct 417 ms 53280 KB Output is correct
9 Correct 415 ms 53248 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 375 ms 16808 KB Output is correct
3 Correct 376 ms 16780 KB Output is correct
4 Correct 414 ms 53228 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 40 ms 5624 KB Output is correct
7 Correct 43 ms 5776 KB Output is correct
8 Correct 46 ms 5652 KB Output is correct
9 Correct 38 ms 5664 KB Output is correct
10 Correct 42 ms 5692 KB Output is correct
11 Correct 41 ms 5696 KB Output is correct
12 Correct 37 ms 5664 KB Output is correct
13 Incorrect 41 ms 5680 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 292 KB Output is correct
2 Correct 40 ms 2960 KB Output is correct
3 Correct 40 ms 2892 KB Output is correct
4 Correct 450 ms 16896 KB Output is correct
5 Incorrect 42 ms 2880 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 5 ms 592 KB Output is correct
3 Correct 5 ms 592 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 4 ms 972 KB Output is correct
17 Correct 52 ms 5676 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 327 ms 16848 KB Output is correct
29 Correct 0 ms 204 KB Output is correct
30 Correct 375 ms 16808 KB Output is correct
31 Correct 376 ms 16780 KB Output is correct
32 Correct 414 ms 53228 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 394 ms 53168 KB Output is correct
35 Correct 407 ms 53276 KB Output is correct
36 Correct 417 ms 53280 KB Output is correct
37 Correct 415 ms 53248 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 40 ms 5624 KB Output is correct
40 Correct 43 ms 5776 KB Output is correct
41 Correct 46 ms 5652 KB Output is correct
42 Correct 38 ms 5664 KB Output is correct
43 Correct 42 ms 5692 KB Output is correct
44 Correct 41 ms 5696 KB Output is correct
45 Correct 37 ms 5664 KB Output is correct
46 Incorrect 41 ms 5680 KB Output isn't correct
47 Halted 0 ms 0 KB -