Submission #1034555

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1034555	2024-07-25T14:51:12 Z	andrei_iorgulescu	Strange Device (APIO19_strange_device)	C++14	35 / 100	1025 ms	69784 KB

strange_device

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n,A,B;
int l[1000005],r[1000005];

signed main()
{
    cin >> n >> A >> B;
    for (int i = 1; i <= n; i++)
        cin >> l[i] >> r[i];
    __int128 AA = A, BB = B;
    __int128 FF = A * B / __gcd(AA,BB + 1);
    if (FF > r[n])
    {
        int sumlen = 0;
        for (int i = 1; i <= n; i++)
            sumlen += r[i] - l[i] + 1;
        cout << sumlen;
    }
    else
    {
        int F = FF;
        for (int i = 1; i <= n; i++)
        {
            if (r[i] - l[i] + 1 >= F)
            {
                cout << F;
                return 0;
            }
        }
        vector<pair<int,int>> h;
        for (int i = 1; i <= n; i++)
        {
            if (r[i] % F >= l[i] % F)
                h.push_back({l[i] % F,r[i] % F});
            else
                h.push_back({0,r[i] % F}),h.push_back({l[i] % F,F - 1});
        }
        sort(h.begin(),h.end());
        int ans = F;
        int rmax = -1;
        if (h.back().second != F - 1)
            ans -= F - 1 - h.back().second;
        for (auto it : h)
        {
            if (it.first > rmax + 1)
                ans -= (it.first - rmax - 1);
            rmax = max(rmax,it.second);
        }
        cout << ans;
    }
    return 0;
}

///cate resturi modulo A * B / gcd(A,B + 1) gasesc?

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	9 ms	1232 KB	Output is correct
3	Correct	16 ms	1224 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	440 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	9 ms	1248 KB	Output is correct
17	Correct	89 ms	7744 KB	Output is correct
18	Incorrect	0 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Incorrect	348 KB	Output isn't correct
6	Halted	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	2 ms	348 KB	Output is correct
4	Correct	1 ms	496 KB	Output is correct
5	Correct	673 ms	57784 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	895 ms	69544 KB	Output is correct
3	Correct	932 ms	69744 KB	Output is correct
4	Correct	815 ms	69564 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	895 ms	69544 KB	Output is correct
3	Correct	932 ms	69744 KB	Output is correct
4	Correct	815 ms	69564 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	862 ms	69540 KB	Output is correct
7	Correct	816 ms	69640 KB	Output is correct
8	Correct	812 ms	69560 KB	Output is correct
9	Correct	882 ms	69576 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	895 ms	69544 KB	Output is correct
3	Correct	932 ms	69744 KB	Output is correct
4	Correct	815 ms	69564 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	86 ms	7676 KB	Output is correct
7	Correct	97 ms	7852 KB	Output is correct
8	Correct	116 ms	7868 KB	Output is correct
9	Correct	87 ms	7876 KB	Output is correct
10	Correct	85 ms	7672 KB	Output is correct
11	Correct	111 ms	7720 KB	Output is correct
12	Correct	88 ms	7876 KB	Output is correct
13	Correct	88 ms	7712 KB	Output is correct
14	Correct	105 ms	7880 KB	Output is correct
15	Correct	114 ms	7848 KB	Output is correct
16	Correct	104 ms	7880 KB	Output is correct
17	Correct	92 ms	7876 KB	Output is correct
18	Correct	956 ms	69656 KB	Output is correct
19	Correct	1025 ms	69568 KB	Output is correct
20	Correct	999 ms	69624 KB	Output is correct
21	Correct	124 ms	7684 KB	Output is correct
22	Correct	92 ms	7900 KB	Output is correct
23	Correct	314 ms	26560 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	94 ms	7668 KB	Output is correct
3	Correct	95 ms	7788 KB	Output is correct
4	Correct	969 ms	69784 KB	Output is correct
5	Correct	92 ms	7880 KB	Output is correct
6	Correct	92 ms	7732 KB	Output is correct
7	Correct	92 ms	7832 KB	Output is correct
8	Correct	96 ms	7656 KB	Output is correct
9	Correct	106 ms	7840 KB	Output is correct
10	Correct	104 ms	7784 KB	Output is correct
11	Correct	100 ms	7772 KB	Output is correct
12	Correct	94 ms	7848 KB	Output is correct
13	Correct	92 ms	7876 KB	Output is correct
14	Correct	941 ms	69752 KB	Output is correct
15	Correct	93 ms	7892 KB	Output is correct
16	Correct	912 ms	69592 KB	Output is correct
17	Correct	880 ms	69756 KB	Output is correct
18	Incorrect	1 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	9 ms	1232 KB	Output is correct
3	Correct	16 ms	1224 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	440 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	9 ms	1248 KB	Output is correct
17	Correct	89 ms	7744 KB	Output is correct
18	Incorrect	0 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #1034555

Compilation message