oj.uz

Submission #1105477

# Submission time Handle Problem Language Result Execution time Memory
1105477 2024-10-26T13:47:27 Z borisAngelov Strange Device (APIO19_strange_device) C++17
15 / 100
 306 ms 19016 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);

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

        long long newL = l % MOD;
        long long newR = r % MOD;

        if (r - l + 1 >= MOD)
        {
            cout << MOD << endl;
            return 0;
        }

        if (l / MOD == r / MOD)
        {
            intervals.push_back({newL, newR});
        }
        else
        {
            intervals.push_back({newL, MOD - 1});
            intervals.push_back({0, newR});
        }
    }

    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:67: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]
   67 |     for (int i = 1; i < intervals.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~
strange_device.cpp:36:10: warning: unused variable 'all' [-Wunused-variable]
   36 |     bool all = false;
      |          ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 3 ms 848 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 456 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 336 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 253 ms 18932 KB Output is correct
3 Correct 242 ms 19008 KB Output is correct
4 Correct 241 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 253 ms 18932 KB Output is correct
3 Correct 242 ms 19008 KB Output is correct
4 Correct 241 ms 18864 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 248 ms 19016 KB Output is correct
7 Correct 237 ms 18864 KB Output is correct
8 Correct 257 ms 18864 KB Output is correct
9 Correct 284 ms 18864 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 253 ms 18932 KB Output is correct
3 Correct 242 ms 19008 KB Output is correct
4 Correct 241 ms 18864 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 27 ms 3516 KB Output is correct
7 Correct 29 ms 3532 KB Output is correct
8 Correct 26 ms 3548 KB Output is correct
9 Correct 28 ms 3532 KB Output is correct
10 Correct 28 ms 3532 KB Output is correct
11 Correct 28 ms 3544 KB Output is correct
12 Correct 28 ms 3532 KB Output is correct
13 Correct 32 ms 3532 KB Output is correct
14 Correct 27 ms 3428 KB Output is correct
15 Incorrect 31 ms 3428 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 3532 KB Output is correct
3 Correct 30 ms 3532 KB Output is correct
4 Correct 306 ms 18864 KB Output is correct
5 Correct 29 ms 3496 KB Output is correct
6 Correct 28 ms 3528 KB Output is correct
7 Correct 29 ms 3532 KB Output is correct
8 Correct 29 ms 3532 KB Output is correct
9 Correct 28 ms 3636 KB Output is correct
10 Correct 29 ms 3532 KB Output is correct
11 Correct 30 ms 3532 KB Output is correct
12 Correct 32 ms 3532 KB Output is correct
13 Correct 31 ms 3532 KB Output is correct
14 Incorrect 289 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 848 KB Output isn't correct
3 Halted 0 ms 0 KB -