oj.uz

Submission #934565

# Submission time Handle Problem Language Result Execution time Memory
934565 2024-02-27T15:11:28 Z Rifal Strange Device (APIO19_strange_device) C++14
65 / 100
 604 ms 76284 KB 
#include <bits/stdc++.h>
#include <fstream>
#define endl '\n'
#define mod 1000000007
#define INF 1000000000000000000
#define INF2 1000000000000000000
//#define ll long long
///#define cin fin
///#define cout fout
using namespace std;
double const EPS = 1e-14;
///ofstream fout("herding.out");
///ifstream fin("herding.in");

int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    long long n, a, b; cin >> n >> a >> b;
    pair<long long, long long> p[n];
    vector<pair<long long,long long>> v;
    long long md;
    if(a > INF/b || b > INF/a) md = (INF + 1ll)/__gcd(a,b+1ll);
    else md = (a*b)/__gcd(a,b+1ll);
   // cout << n << ' ' << a << ' ' << b <<  endl;
   // cout << md << endl;
    bool ok = false;
    for(long long i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
        //cout << i << endl;
        pair<long long, long long> pp;
        pp = p[i];
        p[i].first %= md;
        p[i].second %= md;
        if(p[i].second < p[i].first) {
            if(pp.second-pp.first+1ll >= md) {
                cout << md << endl;
                ok = true;
            }
            v.push_back({p[i].first,0});
            v.push_back({md-1ll,1});
            v.push_back({0,0});
            v.push_back({p[i].second,1});
        }
        else {
            v.push_back({p[i].first,0});
            v.push_back({p[i].second,1});
        }
    }
    if(ok) return 0;
    sort(v.begin(),v.end()); long long cnt = 0;
    long long l = -1, r = 0; 
    long long ans = 0;
    for(int i = 0; i < v.size(); i++) {
        if(v[i].second == 0) {
            cnt++;
            if(l == -1) l = v[i].first;
        }
        else {
            cnt--;
            r = max(v[i].first,r);
        }
        if(cnt == 0) {
            ans += r-l+1ll;
            l = -1, r = 0;
        }
    }
    cout << ans << endl;
    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 4 ms 1504 KB Output is correct
3 Correct 4 ms 1616 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 5 ms 1504 KB Output is correct
17 Correct 45 ms 9668 KB Output is correct
18 Correct 0 ms 348 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 360 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 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 254 ms 61092 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 388 ms 67748 KB Output is correct
3 Correct 393 ms 67940 KB Output is correct
4 Correct 371 ms 67360 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 388 ms 67748 KB Output is correct
3 Correct 393 ms 67940 KB Output is correct
4 Correct 371 ms 67360 KB Output is correct
5 Correct 0 ms 352 KB Output is correct
6 Correct 399 ms 66736 KB Output is correct
7 Correct 414 ms 66684 KB Output is correct
8 Correct 386 ms 68220 KB Output is correct
9 Correct 449 ms 66784 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 388 ms 67748 KB Output is correct
3 Correct 393 ms 67940 KB Output is correct
4 Correct 371 ms 67360 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 41 ms 9220 KB Output is correct
7 Correct 47 ms 10336 KB Output is correct
8 Correct 36 ms 9648 KB Output is correct
9 Correct 38 ms 8696 KB Output is correct
10 Correct 37 ms 8908 KB Output is correct
11 Correct 41 ms 9740 KB Output is correct
12 Correct 37 ms 9932 KB Output is correct
13 Correct 41 ms 8648 KB Output is correct
14 Correct 40 ms 8136 KB Output is correct
15 Correct 44 ms 8648 KB Output is correct
16 Correct 42 ms 8648 KB Output is correct
17 Correct 39 ms 8876 KB Output is correct
18 Correct 408 ms 74212 KB Output is correct
19 Correct 390 ms 76284 KB Output is correct
20 Correct 510 ms 76240 KB Output is correct
21 Correct 46 ms 9428 KB Output is correct
22 Correct 34 ms 9480 KB Output is correct
23 Correct 106 ms 30280 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 41 ms 9348 KB Output is correct
3 Correct 41 ms 9172 KB Output is correct
4 Correct 604 ms 67832 KB Output is correct
5 Correct 42 ms 8136 KB Output is correct
6 Correct 43 ms 8392 KB Output is correct
7 Correct 41 ms 9548 KB Output is correct
8 Correct 45 ms 9124 KB Output is correct
9 Correct 44 ms 8664 KB Output is correct
10 Correct 43 ms 8240 KB Output is correct
11 Correct 51 ms 8912 KB Output is correct
12 Correct 40 ms 9324 KB Output is correct
13 Correct 43 ms 9164 KB Output is correct
14 Correct 499 ms 67436 KB Output is correct
15 Correct 45 ms 8624 KB Output is correct
16 Correct 358 ms 67256 KB Output is correct
17 Correct 395 ms 67164 KB Output is correct
18 Correct 0 ms 344 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 4 ms 1504 KB Output is correct
3 Correct 4 ms 1616 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 5 ms 1504 KB Output is correct
17 Correct 45 ms 9668 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 1 ms 360 KB Output isn't correct
21 Halted 0 ms 0 KB -