oj.uz

Submission #729613

# Submission time Handle Problem Language Result Execution time Memory
729613 2023-04-24T09:40:08 Z danikoynov Strange Device (APIO19_strange_device) C++14
0 / 100
 5000 ms 524288 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e6 + 10;

int n;
ll l[maxn], r[maxn];
ll A, B;

bool tf = false;
ll check(ll a, ll b)
{
    ///cout << a << " " << b << endl;
    if (a < 1e9 && b < 1e9)
        return a * b;
    if (a > b)
        swap(a, b);
    if (b % 2 == 1)
    {
        ll s = check(a, b - 1);
        if (s + a > 1e18)
            tf = true;
        return s + a;
    }
    ll s = check(a, b / 2);
    if (s * 2 > (ll)1e18)
        tf = true;

    return s * 2;
}
void solve()
{
    cin >> n >> A >> B;

    for (int i = 1; i <= n; i ++)
    {
        cin >> l[i] >> r[i];
    }
    check(A, B);

    if (tf)
    {
        while(true);
        ll ans = 0;
        for (int i = 1; i <= n; i ++)
        {
            ans = ans + (r[i] - l[i] + 1);
        }
        cout << ans << endl;
        return;
    }
    unordered_set < ll > st;
    for (int i = 1; i <= n; i ++)
    {

        for (ll j = l[i]; j <= r[i]; j ++)
        {
                 ll x = (j + (j / B)) % A, y = j % B;

            st.insert(x * B + y);
        }
    }

    cout << st.size() << endl;
}

int main()
{
    solve();
    return 0;
}
/**
1  10000 3312452154131231
1 1
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 48 ms 10060 KB Output is correct
3 Correct 67 ms 12044 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 5 ms 852 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 23 ms 4968 KB Output is correct
16 Correct 26 ms 5232 KB Output is correct
17 Correct 146 ms 6820 KB Output is correct
18 Execution timed out 5087 ms 212 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 773 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 70 ms 21924 KB Output is correct
3 Correct 112 ms 21752 KB Output is correct
4 Correct 54 ms 21080 KB Output is correct
5 Execution timed out 5075 ms 58556 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1363 ms 58716 KB Output is correct
3 Runtime error 2216 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1363 ms 58716 KB Output is correct
3 Runtime error 2216 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1363 ms 58716 KB Output is correct
3 Runtime error 2216 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 2623 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 48 ms 10060 KB Output is correct
3 Correct 67 ms 12044 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 5 ms 852 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 23 ms 4968 KB Output is correct
16 Correct 26 ms 5232 KB Output is correct
17 Correct 146 ms 6820 KB Output is correct
18 Execution timed out 5087 ms 212 KB Time limit exceeded
19 Halted 0 ms 0 KB -