Submission #1067603

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1067603	2024-08-20T21:18:44 Z	DeathIsAwe	Strange Device (APIO19_strange_device)	C++17	35 / 100	967 ms	71656 KB

strange_device

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    ll n, a, b; cin >> n >> a >> b;
    vector<pair<ll,ll>> turnedon(n);
    __int128_t divisor = (__int128_t)lcm(a, b + 1);
    __int128_t num = divisor - (__int128_t)(divisor / (b + 1));
    for (int i=0;i<n;i++) {
        cin >> turnedon[i].first >> turnedon[i].second;
    }
    ll limit;
    if (num > 1000000000000000000) {
        limit = 1000000000000000001;
    } else {
        limit = num;
    }


    vector<pair<ll,ll>> ansarr;
    for (int i=0;i<n;i++) {
        if (turnedon[i].second - turnedon[i].first + 1 >= limit) {
            cout << limit;
            return 0;
        }
        turnedon[i].first %= limit; turnedon[i].second %= limit;
        if (turnedon[i].first > turnedon[i].second) {
            ansarr.push_back(make_pair(turnedon[i].first, limit - 1));
            ansarr.push_back(make_pair(0, turnedon[i].second));
        } else {
            ansarr.push_back(make_pair(turnedon[i].first, turnedon[i].second));
        }
    }
    sort(ansarr.begin(), ansarr.end());
    ll ans = 0, tracker = -1;
    for (pair<ll,ll> j: ansarr) {
        if (tracker < j.first) {
            ans += j.second - j.first + 1;
            tracker = j.second;
        } else if (tracker < j.second) {
            ans += j.second - tracker;
            tracker = j.second;
        }
    }
    cout << ans;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	10 ms	1352 KB	Output is correct
3	Correct	16 ms	1240 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 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	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 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	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	10 ms	1356 KB	Output is correct
17	Correct	87 ms	7876 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	352 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	356 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	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	352 KB	Output is correct
5	Correct	594 ms	57912 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	903 ms	69820 KB	Output is correct
3	Correct	866 ms	70448 KB	Output is correct
4	Correct	863 ms	71656 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	903 ms	69820 KB	Output is correct
3	Correct	866 ms	70448 KB	Output is correct
4	Correct	863 ms	71656 KB	Output is correct
5	Correct	0 ms	600 KB	Output is correct
6	Correct	872 ms	70716 KB	Output is correct
7	Correct	862 ms	70728 KB	Output is correct
8	Correct	853 ms	70072 KB	Output is correct
9	Correct	893 ms	71356 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	903 ms	69820 KB	Output is correct
3	Correct	866 ms	70448 KB	Output is correct
4	Correct	863 ms	71656 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	94 ms	7728 KB	Output is correct
7	Correct	88 ms	7860 KB	Output is correct
8	Correct	86 ms	7716 KB	Output is correct
9	Correct	89 ms	7880 KB	Output is correct
10	Correct	105 ms	7876 KB	Output is correct
11	Correct	90 ms	7876 KB	Output is correct
12	Correct	88 ms	7848 KB	Output is correct
13	Correct	98 ms	7860 KB	Output is correct
14	Correct	88 ms	7868 KB	Output is correct
15	Correct	91 ms	7848 KB	Output is correct
16	Correct	90 ms	7880 KB	Output is correct
17	Correct	86 ms	7880 KB	Output is correct
18	Correct	884 ms	70588 KB	Output is correct
19	Correct	862 ms	70840 KB	Output is correct
20	Correct	898 ms	71100 KB	Output is correct
21	Correct	94 ms	7880 KB	Output is correct
22	Correct	90 ms	7876 KB	Output is correct
23	Correct	287 ms	26812 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	90 ms	7736 KB	Output is correct
3	Correct	94 ms	7732 KB	Output is correct
4	Correct	967 ms	70336 KB	Output is correct
5	Correct	97 ms	7880 KB	Output is correct
6	Correct	96 ms	7876 KB	Output is correct
7	Correct	90 ms	7880 KB	Output is correct
8	Correct	97 ms	7876 KB	Output is correct
9	Correct	91 ms	7880 KB	Output is correct
10	Correct	89 ms	7860 KB	Output is correct
11	Correct	91 ms	7860 KB	Output is correct
12	Correct	90 ms	7880 KB	Output is correct
13	Correct	93 ms	7852 KB	Output is correct
14	Correct	911 ms	70584 KB	Output is correct
15	Correct	89 ms	7860 KB	Output is correct
16	Correct	882 ms	69828 KB	Output is correct
17	Correct	855 ms	71096 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	10 ms	1352 KB	Output is correct
3	Correct	16 ms	1240 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 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	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 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	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	10 ms	1356 KB	Output is correct
17	Correct	87 ms	7876 KB	Output is correct
18	Incorrect	0 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #1067603

Compilation message