oj.uz

Submission #1105463

# Submission time Handle Problem Language Result Execution time Memory
1105463 2024-10-26T13:10:56 Z borisAngelov Strange Device (APIO19_strange_device) C++17
10 / 100
 292 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);
    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;

    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 (newL < newR || (newL == newR && l == r))
            {
                intervals.push_back({newL, newR});
            }
            else
            {
                intervals.push_back({newL, MOD - 1});
                intervals.push_back({0, newR});
            }
        }
    }

    if (hasPeriod == false)
    {
        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:66:18: warning: division by zero [-Wdiv-by-zero]
   66 |         cout << 1/0 << endl;
      |                 ~^~
strange_device.cpp:75: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]
   75 |     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 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 Incorrect 1 ms 336 KB Output isn't correct
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 488 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 270 ms 19016 KB Output is correct
3 Correct 245 ms 18864 KB Output is correct
4 Correct 239 ms 18864 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 270 ms 19016 KB Output is correct
3 Correct 245 ms 18864 KB Output is correct
4 Correct 239 ms 18864 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 270 ms 19008 KB Output is correct
7 Correct 247 ms 19012 KB Output is correct
8 Correct 238 ms 18864 KB Output is correct
9 Correct 263 ms 19020 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 270 ms 19016 KB Output is correct
3 Correct 245 ms 18864 KB Output is correct
4 Correct 239 ms 18864 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 34 ms 3508 KB Output is correct
7 Correct 27 ms 3704 KB Output is correct
8 Correct 26 ms 3532 KB Output is correct
9 Correct 26 ms 3536 KB Output is correct
10 Correct 24 ms 3532 KB Output is correct
11 Correct 26 ms 3532 KB Output is correct
12 Correct 25 ms 3532 KB Output is correct
13 Correct 27 ms 3664 KB Output is correct
14 Correct 25 ms 3544 KB Output is correct
15 Incorrect 30 ms 3532 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 30 ms 3540 KB Output is correct
3 Correct 31 ms 3532 KB Output is correct
4 Correct 288 ms 18868 KB Output is correct
5 Correct 31 ms 3532 KB Output is correct
6 Correct 30 ms 3648 KB Output is correct
7 Correct 31 ms 3452 KB Output is correct
8 Correct 32 ms 3532 KB Output is correct
9 Correct 28 ms 3532 KB Output is correct
10 Correct 35 ms 3532 KB Output is correct
11 Correct 30 ms 3532 KB Output is correct
12 Correct 30 ms 3524 KB Output is correct
13 Correct 30 ms 3532 KB Output is correct
14 Incorrect 292 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 724 KB Output isn't correct
3 Halted 0 ms 0 KB -