Submission #465481

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
465481	2021-08-16T08:25:09 Z	alextodoran	Strange Device (APIO19_strange_device)	C++17	35 / 100	985 ms	100244 KB

strange_device

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll gcd (const ll &a, const ll &b)
{
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    ll A, B;
    cin >> n >> A >> B;

    ll per = A * B / gcd(B + 1, A);

    map <ll, int> mars;

    function <void (ll, ll)> proc = [&] (ll l, ll r)
    {
        if(r - l + 1 >= per)
            mars[0]++;
        else
        {
            l %= per;
            r %= per;
            if(l <= r)
            {
                mars[l]++;
                mars[r + 1]--;
            }
            else
            {
                mars[l]++;
                mars[per]--;

                mars[0]++;
                mars[r + 1]--;
            }
        }
    };

    for(int i = 0; i < n; i++)
    {
        ll l, r;
        cin >> l >> r;

        proc(l, r);
    }

    mars[per] = 0;

    ll answer = 0;
    int sum = 0;
    ll pr = 0;

    for(pair <ll, int> x : mars)
    {
        if(sum > 0)
            answer += x.first - pr;
        sum += x.second;
        pr = x.first;
    }

    cout << answer << "\n";

    return 0;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	8 ms	1228 KB	Output is correct
3	Correct	7 ms	1308 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	7 ms	1228 KB	Output is correct
17	Correct	80 ms	10260 KB	Output is correct
18	Incorrect	1 ms	204 KB	Output isn't correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Incorrect	1 ms	204 KB	Output isn't correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	2 ms	356 KB	Output is correct
4	Correct	2 ms	332 KB	Output is correct
5	Correct	344 ms	25420 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	820 ms	100084 KB	Output is correct
3	Correct	860 ms	100204 KB	Output is correct
4	Correct	937 ms	100244 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	820 ms	100084 KB	Output is correct
3	Correct	860 ms	100204 KB	Output is correct
4	Correct	937 ms	100244 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	829 ms	100104 KB	Output is correct
7	Correct	842 ms	100156 KB	Output is correct
8	Correct	852 ms	100144 KB	Output is correct
9	Correct	985 ms	100084 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	820 ms	100084 KB	Output is correct
3	Correct	860 ms	100204 KB	Output is correct
4	Correct	937 ms	100244 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	71 ms	10196 KB	Output is correct
7	Correct	72 ms	10300 KB	Output is correct
8	Correct	80 ms	10196 KB	Output is correct
9	Correct	79 ms	10204 KB	Output is correct
10	Correct	71 ms	10228 KB	Output is correct
11	Correct	77 ms	10216 KB	Output is correct
12	Correct	81 ms	10264 KB	Output is correct
13	Correct	103 ms	10196 KB	Output is correct
14	Correct	89 ms	10264 KB	Output is correct
15	Correct	81 ms	10308 KB	Output is correct
16	Correct	83 ms	10284 KB	Output is correct
17	Correct	75 ms	10208 KB	Output is correct
18	Correct	822 ms	100020 KB	Output is correct
19	Correct	980 ms	100116 KB	Output is correct
20	Correct	926 ms	100012 KB	Output is correct
21	Correct	73 ms	10180 KB	Output is correct
22	Correct	78 ms	10192 KB	Output is correct
23	Correct	142 ms	12832 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	79 ms	10200 KB	Output is correct
3	Correct	77 ms	10240 KB	Output is correct
4	Correct	873 ms	100184 KB	Output is correct
5	Correct	81 ms	10260 KB	Output is correct
6	Correct	80 ms	10208 KB	Output is correct
7	Correct	82 ms	10248 KB	Output is correct
8	Correct	79 ms	10224 KB	Output is correct
9	Correct	83 ms	10264 KB	Output is correct
10	Correct	77 ms	10368 KB	Output is correct
11	Correct	77 ms	10232 KB	Output is correct
12	Correct	82 ms	10284 KB	Output is correct
13	Correct	84 ms	10200 KB	Output is correct
14	Correct	975 ms	100048 KB	Output is correct
15	Correct	74 ms	10308 KB	Output is correct
16	Correct	820 ms	100120 KB	Output is correct
17	Correct	820 ms	100016 KB	Output is correct
18	Incorrect	0 ms	204 KB	Output isn't correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	8 ms	1228 KB	Output is correct
3	Correct	7 ms	1308 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	7 ms	1228 KB	Output is correct
17	Correct	80 ms	10260 KB	Output is correct
18	Incorrect	1 ms	204 KB	Output isn't correct

Submission #465481

Compilation message