oj.uz

Submission #934563

# Submission time Handle Problem Language Result Execution time Memory
934563 2024-02-27T15:06:56 Z Rifal Strange Device (APIO19_strange_device) C++14
65 / 100
 559 ms 81692 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) md = (INF + 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 344 KB Output is correct
2 Correct 4 ms 1500 KB Output is correct
3 Correct 4 ms 1396 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 5 ms 1504 KB Output is correct
17 Correct 48 ms 9472 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 1 ms 344 KB Output is correct
2 Incorrect 0 ms 452 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 256 ms 66964 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 559 ms 76384 KB Output is correct
3 Correct 410 ms 77152 KB Output is correct
4 Correct 408 ms 77312 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 559 ms 76384 KB Output is correct
3 Correct 410 ms 77152 KB Output is correct
4 Correct 408 ms 77312 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 434 ms 76284 KB Output is correct
7 Correct 390 ms 75892 KB Output is correct
8 Correct 437 ms 76768 KB Output is correct
9 Correct 453 ms 76996 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 559 ms 76384 KB Output is correct
3 Correct 410 ms 77152 KB Output is correct
4 Correct 408 ms 77312 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 39 ms 10184 KB Output is correct
7 Correct 44 ms 8648 KB Output is correct
8 Correct 39 ms 10256 KB Output is correct
9 Correct 37 ms 9684 KB Output is correct
10 Correct 40 ms 8660 KB Output is correct
11 Correct 49 ms 9052 KB Output is correct
12 Correct 40 ms 10184 KB Output is correct
13 Correct 52 ms 9668 KB Output is correct
14 Correct 39 ms 9940 KB Output is correct
15 Correct 49 ms 10188 KB Output is correct
16 Correct 42 ms 8656 KB Output is correct
17 Correct 39 ms 9428 KB Output is correct
18 Correct 421 ms 77632 KB Output is correct
19 Correct 377 ms 81692 KB Output is correct
20 Correct 498 ms 80596 KB Output is correct
21 Correct 45 ms 9684 KB Output is correct
22 Correct 34 ms 9260 KB Output is correct
23 Correct 113 ms 32800 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 42 ms 10700 KB Output is correct
3 Correct 43 ms 9932 KB Output is correct
4 Correct 549 ms 76632 KB Output is correct
5 Correct 45 ms 9444 KB Output is correct
6 Correct 46 ms 9188 KB Output is correct
7 Correct 42 ms 9500 KB Output is correct
8 Correct 54 ms 8644 KB Output is correct
9 Correct 40 ms 10152 KB Output is correct
10 Correct 47 ms 9400 KB Output is correct
11 Correct 45 ms 8904 KB Output is correct
12 Correct 38 ms 8908 KB Output is correct
13 Correct 43 ms 8648 KB Output is correct
14 Correct 464 ms 76192 KB Output is correct
15 Correct 44 ms 10444 KB Output is correct
16 Correct 411 ms 76680 KB Output is correct
17 Correct 419 ms 77196 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 344 KB Output is correct
2 Correct 4 ms 1500 KB Output is correct
3 Correct 4 ms 1396 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 5 ms 1504 KB Output is correct
17 Correct 48 ms 9472 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Incorrect 0 ms 452 KB Output isn't correct
21 Halted 0 ms 0 KB -