oj.uz

Submission #1105462

# Submission time Handle Problem Language Result Execution time Memory
1105462 2024-10-26T13:10:15 Z borisAngelov Strange Device (APIO19_strange_device) C++17
10 / 100
 386 ms 54208 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)
      |                     ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 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 -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 508 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 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 286 ms 54012 KB Output is correct
3 Correct 272 ms 54188 KB Output is correct
4 Correct 280 ms 54096 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 286 ms 54012 KB Output is correct
3 Correct 272 ms 54188 KB Output is correct
4 Correct 280 ms 54096 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 282 ms 54184 KB Output is correct
7 Correct 274 ms 54208 KB Output is correct
8 Correct 270 ms 54068 KB Output is correct
9 Correct 367 ms 54192 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 286 ms 54012 KB Output is correct
3 Correct 272 ms 54188 KB Output is correct
4 Correct 280 ms 54096 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 31 ms 6348 KB Output is correct
7 Correct 35 ms 6336 KB Output is correct
8 Correct 31 ms 6332 KB Output is correct
9 Correct 32 ms 6348 KB Output is correct
10 Correct 35 ms 6348 KB Output is correct
11 Correct 32 ms 6348 KB Output is correct
12 Correct 30 ms 6340 KB Output is correct
13 Correct 33 ms 6308 KB Output is correct
14 Correct 31 ms 6336 KB Output is correct
15 Incorrect 35 ms 6340 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 34 ms 6348 KB Output is correct
3 Correct 38 ms 6336 KB Output is correct
4 Correct 386 ms 54188 KB Output is correct
5 Correct 41 ms 6348 KB Output is correct
6 Correct 34 ms 6348 KB Output is correct
7 Correct 39 ms 6196 KB Output is correct
8 Correct 34 ms 6348 KB Output is correct
9 Correct 45 ms 6340 KB Output is correct
10 Correct 35 ms 6348 KB Output is correct
11 Correct 33 ms 6112 KB Output is correct
12 Correct 30 ms 6340 KB Output is correct
13 Correct 35 ms 6340 KB Output is correct
14 Incorrect 366 ms 54180 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 1104 KB Output isn't correct
3 Halted 0 ms 0 KB -