Submission #558343

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
558343	2022-05-07T06:39:06 Z	InternetPerson10	Strange Device (APIO19_strange_device)	C++17	35 / 100	836 ms	100208 KB

strange_device

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q;
    ll a, b;
    cin >> q >> a >> b;
    __int128 cyc = a * b / __gcd(a, b + 1);
    ll MOD = 1e18 + 9;
    if(MOD > cyc) MOD = cyc;
    map<ll, int> m;
    while(q--) {
        ll l, r;
        cin >> l >> r;
        r++;
        if(r - l >= MOD) {
            m[0]++;
            m[MOD]--;
        }
        else if(r/MOD != l/MOD) {
            m[l%MOD]++;
            m[0]++;
            m[MOD]--;
            m[r%MOD]--;
        }
        else {
            m[l%MOD]++;
            m[r%MOD]--;
        }
    }
    ll ans = 0, x = 0;
    for(auto p : m) {
        if(x == 0) ans -= p.first;
        x += p.second;
        if(x == 0) ans += p.first;
    }
    cout << ans << '\n';
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	6 ms	1236 KB	Output is correct
3	Correct	7 ms	1236 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	324 KB	Output is correct
8	Correct	1 ms	324 KB	Output is correct
9	Correct	1 ms	324 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	6 ms	1236 KB	Output is correct
17	Correct	75 ms	10220 KB	Output is correct
18	Incorrect	0 ms	212 KB	Output isn't correct
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	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Incorrect	1 ms	212 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct
5	Correct	277 ms	25552 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	773 ms	68300 KB	Output is correct
3	Correct	793 ms	68760 KB	Output is correct
4	Correct	776 ms	100064 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	773 ms	68300 KB	Output is correct
3	Correct	793 ms	68760 KB	Output is correct
4	Correct	776 ms	100064 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	836 ms	100120 KB	Output is correct
7	Correct	732 ms	100064 KB	Output is correct
8	Correct	756 ms	100208 KB	Output is correct
9	Correct	789 ms	100064 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	773 ms	68300 KB	Output is correct
3	Correct	793 ms	68760 KB	Output is correct
4	Correct	776 ms	100064 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	64 ms	10180 KB	Output is correct
7	Correct	64 ms	10232 KB	Output is correct
8	Correct	62 ms	10304 KB	Output is correct
9	Correct	70 ms	10188 KB	Output is correct
10	Correct	62 ms	10312 KB	Output is correct
11	Correct	60 ms	10224 KB	Output is correct
12	Correct	58 ms	10200 KB	Output is correct
13	Correct	69 ms	10276 KB	Output is correct
14	Correct	77 ms	10312 KB	Output is correct
15	Correct	80 ms	10256 KB	Output is correct
16	Correct	70 ms	10224 KB	Output is correct
17	Correct	66 ms	10288 KB	Output is correct
18	Correct	733 ms	100172 KB	Output is correct
19	Correct	737 ms	100076 KB	Output is correct
20	Correct	824 ms	100008 KB	Output is correct
21	Correct	71 ms	10304 KB	Output is correct
22	Correct	67 ms	10180 KB	Output is correct
23	Correct	113 ms	12844 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	74 ms	10184 KB	Output is correct
3	Correct	80 ms	10208 KB	Output is correct
4	Correct	757 ms	68440 KB	Output is correct
5	Correct	74 ms	10260 KB	Output is correct
6	Correct	75 ms	10196 KB	Output is correct
7	Correct	77 ms	10188 KB	Output is correct
8	Correct	70 ms	10260 KB	Output is correct
9	Correct	69 ms	10184 KB	Output is correct
10	Correct	63 ms	10308 KB	Output is correct
11	Correct	65 ms	10228 KB	Output is correct
12	Correct	72 ms	10188 KB	Output is correct
13	Correct	88 ms	10212 KB	Output is correct
14	Correct	774 ms	100080 KB	Output is correct
15	Correct	61 ms	10252 KB	Output is correct
16	Correct	728 ms	100164 KB	Output is correct
17	Correct	751 ms	100052 KB	Output is correct
18	Incorrect	1 ms	212 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	212 KB	Output is correct
2	Correct	6 ms	1236 KB	Output is correct
3	Correct	7 ms	1236 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	324 KB	Output is correct
8	Correct	1 ms	324 KB	Output is correct
9	Correct	1 ms	324 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	6 ms	1236 KB	Output is correct
17	Correct	75 ms	10220 KB	Output is correct
18	Incorrect	0 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #558343

Compilation message