oj.uz

Submission #977367

# Submission time Handle Problem Language Result Execution time Memory
977367 2024-05-07T19:40:25 Z notyou Strange Device (APIO19_strange_device) C++17
65 / 100
 380 ms 53272 KB 
#include <bits/stdc++.h>

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define pb push_back
#define vl vector<ll>
#define fi first
#define se second
#define in insert
#define all(v) v.begin(), v.end()
#define bpc(x) __builtin_popcount(x)
#define endl "\n"

using namespace std;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const int sz = 4e5 + 5;
const int LG = 21;
// using namespace __gnu_pbds;
// tree <ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> rbt;
ll gcd(ll a, ll b){
    return __gcd(a, b);
}
ll get(ll a, ll b){
    ll c = (a / gcd(a, b + 1)), hi = inf / b;
    if(c > hi){
        c = inf;
    }
    else{
        c *= b;
    }
    return c;
}
void solve(){
    ll n, a, b, i, l, r;
    cin >> n >> a >> b;
    if(a == 1 && b == 1){
        cout << 1 << endl;
        return ;
    }
    ll x = get(a, b);
    vector<array<ll, 2>> v;
    bool ok = 1;
    for(i = 1; i <= n; i++){
        cin >> l >> r;
        ok &= ((r - l + 1) >= x);
        l %= x;
        r %= x;
        if(r < l){
            v.pb({l, x - 1});
            v.pb({0, r});
        }
        else{
            v.pb({l, r});
        }
    }
    sort(all(v));
    ll s = 0, hi = -1;
    for(i = 0; i < v.size(); i++){
        // cout << v[i][0] << ' ' << v[i][1] << endl;
        if(v[i][0] > hi){
            s += (v[i][1] - v[i][0] + 1);
            hi = v[i][1];
        }
        else if(v[i][1] > hi){
            s += (v[i][1] - hi);
            hi = v[i][1];
        }
    }
    cout << s << endl;


}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}
/*
3 3 3
4 4
7 9
17 18
*/

Compilation message

strange_device.cpp: In function 'void solve()':
strange_device.cpp:61:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(i = 0; i < v.size(); i++){
      |                ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct
3 Correct 4 ms 1116 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 0 ms 436 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 448 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 36 ms 5656 KB Output is correct
18 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 244 ms 38780 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 334 ms 49380 KB Output is correct
3 Correct 318 ms 53164 KB Output is correct
4 Correct 312 ms 53204 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 334 ms 49380 KB Output is correct
3 Correct 318 ms 53164 KB Output is correct
4 Correct 312 ms 53204 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 319 ms 53144 KB Output is correct
7 Correct 320 ms 53168 KB Output is correct
8 Correct 318 ms 53228 KB Output is correct
9 Correct 360 ms 53272 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 334 ms 49380 KB Output is correct
3 Correct 318 ms 53164 KB Output is correct
4 Correct 312 ms 53204 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 33 ms 5652 KB Output is correct
7 Correct 34 ms 5836 KB Output is correct
8 Correct 32 ms 5640 KB Output is correct
9 Correct 32 ms 5832 KB Output is correct
10 Correct 34 ms 5832 KB Output is correct
11 Correct 34 ms 5820 KB Output is correct
12 Correct 31 ms 5752 KB Output is correct
13 Correct 34 ms 5832 KB Output is correct
14 Correct 32 ms 5060 KB Output is correct
15 Correct 36 ms 5064 KB Output is correct
16 Correct 34 ms 5116 KB Output is correct
17 Correct 36 ms 5340 KB Output is correct
18 Correct 328 ms 44964 KB Output is correct
19 Correct 321 ms 44788 KB Output is correct
20 Correct 349 ms 44400 KB Output is correct
21 Correct 36 ms 5064 KB Output is correct
22 Correct 30 ms 5128 KB Output is correct
23 Correct 99 ms 17004 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 40 ms 5508 KB Output is correct
3 Correct 34 ms 5320 KB Output is correct
4 Correct 380 ms 44536 KB Output is correct
5 Correct 40 ms 5540 KB Output is correct
6 Correct 35 ms 5216 KB Output is correct
7 Correct 34 ms 5216 KB Output is correct
8 Correct 36 ms 5076 KB Output is correct
9 Correct 38 ms 5068 KB Output is correct
10 Correct 35 ms 5080 KB Output is correct
11 Correct 44 ms 5032 KB Output is correct
12 Correct 31 ms 5072 KB Output is correct
13 Correct 35 ms 5064 KB Output is correct
14 Correct 361 ms 44460 KB Output is correct
15 Correct 36 ms 5032 KB Output is correct
16 Correct 318 ms 44460 KB Output is correct
17 Correct 321 ms 45408 KB Output is correct
18 Correct 1 ms 344 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct
3 Correct 4 ms 1116 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 0 ms 436 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 448 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 36 ms 5656 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 1 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -