oj.uz

Submission #1105473

# Submission time Handle Problem Language Result Execution time Memory
1105473 2024-10-26T13:21:06 Z borisAngelov Strange Device (APIO19_strange_device) C++17
15 / 100
 303 ms 52124 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);
    bool hasPeriod = true;

    if (MAXMOD / MOD < b)
    {
        hasPeriod = false;
    }
    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;

        if (hasPeriod == false)
        {
            ans += (r - l + 1);
        }
        else
        {
            long long newL = l % MOD;
            long long newR = r % MOD;

            if (l / MOD == r / MOD)
            {
                intervals.push_back({newL, newR});
            }
            else if (l / MOD + 1 == r / MOD && newL > newR)
            {
                intervals.push_back({newL, MOD - 1});
                intervals.push_back({0, newR});
            }
            else
            {
                all = true;
                ans = MOD;
            }
        }
    }

    if (hasPeriod == false)
    {
        cout << ans << endl;
        return 0;
    }

    if (all == true)
    {
        cout << ans << endl;
        return 0;
    }

    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:86: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]
   86 |     for (int i = 1; i < intervals.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 3 ms 688 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 336 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 504 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 275 ms 19020 KB Output is correct
3 Correct 280 ms 18864 KB Output is correct
4 Correct 270 ms 52124 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 275 ms 19020 KB Output is correct
3 Correct 280 ms 18864 KB Output is correct
4 Correct 270 ms 52124 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 265 ms 19024 KB Output is correct
7 Correct 256 ms 35480 KB Output is correct
8 Correct 250 ms 18864 KB Output is correct
9 Correct 284 ms 23236 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 275 ms 19020 KB Output is correct
3 Correct 280 ms 18864 KB Output is correct
4 Correct 270 ms 52124 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 27 ms 3584 KB Output is correct
7 Correct 29 ms 6344 KB Output is correct
8 Correct 25 ms 3532 KB Output is correct
9 Correct 27 ms 3600 KB Output is correct
10 Correct 25 ms 3528 KB Output is correct
11 Correct 32 ms 3532 KB Output is correct
12 Correct 32 ms 5644 KB Output is correct
13 Correct 39 ms 3496 KB Output is correct
14 Correct 35 ms 3524 KB Output is correct
15 Incorrect 31 ms 6348 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 28 ms 3624 KB Output is correct
3 Correct 28 ms 3532 KB Output is correct
4 Correct 303 ms 18864 KB Output is correct
5 Correct 28 ms 3532 KB Output is correct
6 Correct 30 ms 3532 KB Output is correct
7 Correct 28 ms 3532 KB Output is correct
8 Correct 29 ms 3532 KB Output is correct
9 Correct 28 ms 3532 KB Output is correct
10 Correct 31 ms 3532 KB Output is correct
11 Correct 37 ms 3524 KB Output is correct
12 Correct 34 ms 3548 KB Output is correct
13 Correct 34 ms 5840 KB Output is correct
14 Incorrect 297 ms 18864 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 3 ms 688 KB Output isn't correct
3 Halted 0 ms 0 KB -