oj.uz

Submission #1105476

# Submission time Handle Problem Language Result Execution time Memory
1105476 2024-10-26T13:43:41 Z borisAngelov Strange Device (APIO19_strange_device) C++17
10 / 100
 304 ms 19028 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 << 1/0 << endl;
        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:78:18: warning: division by zero [-Wdiv-by-zero]
   78 |         cout << 1/0 << endl;
      |                 ~^~
strange_device.cpp:87: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]
   87 |     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 4 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Runtime error 1 ms 592 KB Execution killed with signal 8
3 Halted 0 ms 0 KB -

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 269 ms 19028 KB Output is correct
3 Correct 275 ms 18864 KB Output is correct
4 Correct 278 ms 18860 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 269 ms 19028 KB Output is correct
3 Correct 275 ms 18864 KB Output is correct
4 Correct 278 ms 18860 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 291 ms 18860 KB Output is correct
7 Correct 281 ms 18868 KB Output is correct
8 Correct 274 ms 18864 KB Output is correct
9 Correct 304 ms 18896 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 269 ms 19028 KB Output is correct
3 Correct 275 ms 18864 KB Output is correct
4 Correct 278 ms 18860 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 28 ms 3532 KB Output is correct
7 Correct 33 ms 3444 KB Output is correct
8 Correct 27 ms 3532 KB Output is correct
9 Correct 33 ms 3524 KB Output is correct
10 Correct 28 ms 3532 KB Output is correct
11 Correct 35 ms 3532 KB Output is correct
12 Correct 29 ms 3532 KB Output is correct
13 Correct 31 ms 3484 KB Output is correct
14 Correct 28 ms 3532 KB Output is correct
15 Incorrect 31 ms 3700 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 504 KB Output is correct
2 Correct 32 ms 3672 KB Output is correct
3 Correct 37 ms 3596 KB Output is correct
4 Correct 297 ms 18864 KB Output is correct
5 Correct 28 ms 3532 KB Output is correct
6 Correct 28 ms 3532 KB Output is correct
7 Correct 28 ms 3544 KB Output is correct
8 Correct 29 ms 3532 KB Output is correct
9 Correct 28 ms 3784 KB Output is correct
10 Correct 28 ms 3532 KB Output is correct
11 Correct 28 ms 3700 KB Output is correct
12 Correct 28 ms 3532 KB Output is correct
13 Correct 28 ms 3532 KB Output is correct
14 Incorrect 270 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 4 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -