oj.uz

Submission #1105483

# Submission time Handle Problem Language Result Execution time Memory
1105483 2024-10-26T13:55:25 Z borisAngelov Strange Device (APIO19_strange_device) C++17
15 / 100
 355 ms 19020 KB 
#include <bits/stdc++.h>

using namespace std;

const long long MAXMOD = 1e18 + 7;

int n;
long long a, b;

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> a >> b;

    long long MOD = a / __gcd(a, b + 1);

    if (MOD > MAXMOD / b)
    {
        MOD = MAXMOD;
    }
    else
    {
        MOD *= b; // a * b / gcd(a, b + 1)
    }

    vector<pair<long long, long long>> intervals;
    long long ans = 0;
    bool all = false;

    for (int i = 1; i <= n; ++i)
    {
        long long l, r;
        cin >> l >> r;

        long long newL = l % MOD;
        long long newR = r % MOD;

        if (r - l + 1 >= MOD)
        {
            cout << MOD << endl;
            return 0;
        }

        if (newL <= newR)
        {
            intervals.push_back({newL, newR});
        }
        else
        {
            intervals.push_back({newL, MOD - 1});
            intervals.push_back({0, newR});
        }
    }

    sort(intervals.begin(), intervals.end());

    long long from = intervals[0].first, to = intervals[0].second;

    for (int i = 1; i < intervals.size(); ++i)
    {
        if (intervals[i].first <= to)
        {
            to = intervals[i].second;
        }
        else
        {
            ans += (to - from + 1);
            from = intervals[i].first;
            to = intervals[i].second;
        }
    }

    ans += (to - from + 1);
    cout << ans << endl;

    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:67:23: 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]
   67 |     for (int i = 1; i < intervals.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~
strange_device.cpp:36:10: warning: unused variable 'all' [-Wunused-variable]
   36 |     bool all = false;
      |          ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 4 ms 736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 259 ms 18884 KB Output is correct
3 Correct 254 ms 18864 KB Output is correct
4 Correct 323 ms 19004 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 259 ms 18884 KB Output is correct
3 Correct 254 ms 18864 KB Output is correct
4 Correct 323 ms 19004 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 294 ms 18944 KB Output is correct
7 Correct 267 ms 19020 KB Output is correct
8 Correct 319 ms 18932 KB Output is correct
9 Correct 355 ms 18876 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 259 ms 18884 KB Output is correct
3 Correct 254 ms 18864 KB Output is correct
4 Correct 323 ms 19004 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 28 ms 3496 KB Output is correct
7 Correct 34 ms 3532 KB Output is correct
8 Correct 25 ms 3592 KB Output is correct
9 Correct 28 ms 3504 KB Output is correct
10 Correct 27 ms 3588 KB Output is correct
11 Correct 28 ms 3532 KB Output is correct
12 Correct 38 ms 3548 KB Output is correct
13 Correct 30 ms 3600 KB Output is correct
14 Correct 31 ms 3532 KB Output is correct
15 Incorrect 36 ms 3784 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 33 ms 3532 KB Output is correct
3 Correct 33 ms 3652 KB Output is correct
4 Correct 324 ms 18864 KB Output is correct
5 Correct 27 ms 3532 KB Output is correct
6 Correct 31 ms 3420 KB Output is correct
7 Correct 37 ms 3532 KB Output is correct
8 Correct 30 ms 3532 KB Output is correct
9 Correct 27 ms 3532 KB Output is correct
10 Correct 28 ms 3532 KB Output is correct
11 Correct 28 ms 3484 KB Output is correct
12 Correct 24 ms 3532 KB Output is correct
13 Correct 27 ms 3532 KB Output is correct
14 Incorrect 319 ms 18824 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 4 ms 736 KB Output isn't correct
3 Halted 0 ms 0 KB -