Submission #587765

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
587765	2022-07-02T10:44:12 Z	stevancv	Strange Device (APIO19_strange_device)	C++14	35 / 100	960 ms	100316 KB

strange_device

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int q;
    ll a, b;
    cin >> q >> a >> b;
    ll p = (a / __gcd(a, b + 1)) * b;
    set<pair<ll, ll>> s;
    function<void(ll, ll)> Add = [&] (ll l, ll r) {
        auto it = s.lower_bound({l, 0});
        ll mn = 2e18; ll mx = -1;
        while (it != s.end() && (*it).second <= r) {
            smin(mn, (*it).second);
            smax(mx, (*it).first);
            it = s.erase(it);
        }
        smin(mn, l);
        smax(mx, r);
        s.insert({mx, mn});
    };
    while (q--) {
        ll l, r;
        cin >> l >> r;
        if (r - l + 1 >= p) {Add(0, p - 1); continue;}
        l %= p;
        r %= p;
        if (l > r) {Add(l, p - 1); Add(0, r);}
        else Add(l, r);
    }
    ll ans = 0;
    for (auto u : s) {
        ans += u.first - u.second + 1;
    }
    cout << ans << en;
    return 0;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	7 ms	1232 KB	Output is correct
3	Correct	6 ms	1256 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	5 ms	1216 KB	Output is correct
17	Correct	63 ms	10188 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	0 ms	212 KB	Output is correct
2	Correct	1 ms	320 KB	Output is correct
3	Correct	1 ms	320 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	1 ms	376 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	297 ms	25372 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	667 ms	100116 KB	Output is correct
3	Correct	726 ms	100020 KB	Output is correct
4	Correct	835 ms	100192 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	667 ms	100116 KB	Output is correct
3	Correct	726 ms	100020 KB	Output is correct
4	Correct	835 ms	100192 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	663 ms	100204 KB	Output is correct
7	Correct	733 ms	99984 KB	Output is correct
8	Correct	703 ms	100252 KB	Output is correct
9	Correct	818 ms	100120 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	667 ms	100116 KB	Output is correct
3	Correct	726 ms	100020 KB	Output is correct
4	Correct	835 ms	100192 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	59 ms	10208 KB	Output is correct
7	Correct	55 ms	10156 KB	Output is correct
8	Correct	77 ms	10224 KB	Output is correct
9	Correct	83 ms	10188 KB	Output is correct
10	Correct	54 ms	10252 KB	Output is correct
11	Correct	58 ms	10152 KB	Output is correct
12	Correct	59 ms	10188 KB	Output is correct
13	Correct	67 ms	10244 KB	Output is correct
14	Correct	59 ms	10196 KB	Output is correct
15	Correct	89 ms	10224 KB	Output is correct
16	Correct	66 ms	10316 KB	Output is correct
17	Correct	64 ms	10212 KB	Output is correct
18	Correct	680 ms	100012 KB	Output is correct
19	Correct	735 ms	100096 KB	Output is correct
20	Correct	776 ms	100316 KB	Output is correct
21	Correct	67 ms	10220 KB	Output is correct
22	Correct	61 ms	10212 KB	Output is correct
23	Correct	134 ms	12852 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	69 ms	10144 KB	Output is correct
3	Correct	75 ms	10216 KB	Output is correct
4	Correct	774 ms	99996 KB	Output is correct
5	Correct	74 ms	10164 KB	Output is correct
6	Correct	92 ms	10192 KB	Output is correct
7	Correct	71 ms	10276 KB	Output is correct
8	Correct	67 ms	10160 KB	Output is correct
9	Correct	70 ms	10188 KB	Output is correct
10	Correct	71 ms	10220 KB	Output is correct
11	Correct	72 ms	10216 KB	Output is correct
12	Correct	64 ms	10212 KB	Output is correct
13	Correct	68 ms	10164 KB	Output is correct
14	Correct	960 ms	99984 KB	Output is correct
15	Correct	56 ms	9612 KB	Output is correct
16	Correct	708 ms	100088 KB	Output is correct
17	Correct	696 ms	100088 KB	Output is correct
18	Incorrect	0 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	7 ms	1232 KB	Output is correct
3	Correct	6 ms	1256 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	5 ms	1216 KB	Output is correct
17	Correct	63 ms	10188 KB	Output is correct
18	Incorrect	0 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #587765

Compilation message