Submission #1105465

# Submission time Handle Problem Language Result Execution time Memory
1105465 2024-10-26T13:12:22 Z borisAngelov Strange Device (APIO19_strange_device) C++17
10 / 100
321 ms 48808 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 << 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:74: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]
   74 |     for (int i = 1; i < intervals.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 4 ms 1104 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 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 -
# 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 -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 272 ms 37948 KB Output is correct
3 Correct 286 ms 18864 KB Output is correct
4 Correct 298 ms 48808 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 272 ms 37948 KB Output is correct
3 Correct 286 ms 18864 KB Output is correct
4 Correct 298 ms 48808 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 278 ms 18864 KB Output is correct
7 Correct 258 ms 37552 KB Output is correct
8 Correct 309 ms 18864 KB Output is correct
9 Correct 293 ms 19052 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 272 ms 37948 KB Output is correct
3 Correct 286 ms 18864 KB Output is correct
4 Correct 298 ms 48808 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 31 ms 6348 KB Output is correct
7 Correct 28 ms 3532 KB Output is correct
8 Correct 25 ms 3532 KB Output is correct
9 Correct 30 ms 3532 KB Output is correct
10 Correct 32 ms 6204 KB Output is correct
11 Correct 35 ms 6100 KB Output is correct
12 Correct 31 ms 3532 KB Output is correct
13 Correct 35 ms 6084 KB Output is correct
14 Correct 30 ms 6208 KB Output is correct
15 Incorrect 31 ms 3532 KB Output isn't correct
16 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 35 ms 5580 KB Output is correct
3 Correct 58 ms 6080 KB Output is correct
4 Correct 321 ms 21840 KB Output is correct
5 Correct 33 ms 5684 KB Output is correct
6 Correct 54 ms 5572 KB Output is correct
7 Correct 38 ms 4532 KB Output is correct
8 Correct 58 ms 5644 KB Output is correct
9 Correct 31 ms 2508 KB Output is correct
10 Correct 45 ms 4548 KB Output is correct
11 Correct 31 ms 3700 KB Output is correct
12 Correct 28 ms 2508 KB Output is correct
13 Correct 35 ms 6084 KB Output is correct
14 Incorrect 299 ms 37552 KB Output isn't correct
15 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 4 ms 1104 KB Output isn't correct
3 Halted 0 ms 0 KB -