Submission #785869

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
785869	2023-07-17T17:15:36 Z	aykhn	Strange Device (APIO19_strange_device)	C++14	35 / 100	1357 ms	100012 KB

strange_device

#include <bits/stdc++.h>

// author: aykhn

using namespace std;

typedef long long ll;

#define TC int t; cin >> t; while (t--) _();
#define OPT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define mpr make_pair
#define eb emplace_back
#define new int32_t
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define int ll
#define ins insert
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount

int n, a, b;

/*int x(int i)
{
    return (i + i/b) % a;
}
int y(int i)
{
    return i % b;
}*/

new main()
{
    cin >> n >> a >> b;

    int x = a/__gcd(a, b + 1) * b;

    set<pii> s;

    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;

        if (b - a + 1 >= x)
        {
            s.ins(mpr(0, x - 1));
        }
        else
        {
            int l = a % x;
            int r = b % x;

            if (l <= r)
            {
                s.ins(mpr(l, r));
            }
            else
            {
                s.ins(mpr(l, x - 1));
                s.ins(mpr(0, r));
            }
        }
    }

    set<pii> nw;

    while (s.size() > 1)
    {
        auto it = s.begin();
        pii a = *it;
        it++;
        pii b = *it;

        if (max(a.fi, b.fi) <= min(a.se, b.se))
        {
            s.erase(s.begin());
            s.erase(s.begin());
            s.ins(mpr(min(a.fi, b.fi), max(a.se, b.se)));
        }
        else
        {
            s.erase(s.begin());
            nw.ins(a);
        }
    }

    nw.ins(*s.begin());

    int res = 0;

    for (pii a : nw)
    {
        res += a.se - a.fi + 1;
    }

    cout << res << endl;
    return 0;
}
// 4, 5 -> 10;
// 3, 6 -> 18;

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	12 ms	1236 KB	Output is correct
3	Correct	12 ms	1236 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	300 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 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	212 KB	Output is correct
16	Correct	12 ms	1236 KB	Output is correct
17	Correct	129 ms	10228 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	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Incorrect	0 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	2 ms	340 KB	Output is correct
4	Correct	2 ms	308 KB	Output is correct
5	Correct	718 ms	25348 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	1301 ms	100000 KB	Output is correct
3	Correct	1273 ms	99968 KB	Output is correct
4	Correct	1326 ms	100012 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	1301 ms	100000 KB	Output is correct
3	Correct	1273 ms	99968 KB	Output is correct
4	Correct	1326 ms	100012 KB	Output is correct
5	Correct	1 ms	296 KB	Output is correct
6	Correct	1254 ms	100004 KB	Output is correct
7	Correct	1297 ms	99984 KB	Output is correct
8	Correct	1357 ms	99912 KB	Output is correct
9	Correct	1344 ms	99928 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	1301 ms	100000 KB	Output is correct
3	Correct	1273 ms	99968 KB	Output is correct
4	Correct	1326 ms	100012 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	116 ms	10188 KB	Output is correct
7	Correct	119 ms	10200 KB	Output is correct
8	Correct	121 ms	10132 KB	Output is correct
9	Correct	127 ms	10160 KB	Output is correct
10	Correct	116 ms	10176 KB	Output is correct
11	Correct	121 ms	10176 KB	Output is correct
12	Correct	121 ms	10248 KB	Output is correct
13	Correct	121 ms	10232 KB	Output is correct
14	Correct	116 ms	10200 KB	Output is correct
15	Correct	126 ms	10188 KB	Output is correct
16	Correct	122 ms	10156 KB	Output is correct
17	Correct	124 ms	10132 KB	Output is correct
18	Correct	1318 ms	99972 KB	Output is correct
19	Correct	1347 ms	99984 KB	Output is correct
20	Correct	1338 ms	99988 KB	Output is correct
21	Correct	120 ms	10200 KB	Output is correct
22	Correct	120 ms	10256 KB	Output is correct
23	Correct	326 ms	12804 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	123 ms	10220 KB	Output is correct
3	Correct	124 ms	10208 KB	Output is correct
4	Correct	1328 ms	99952 KB	Output is correct
5	Correct	122 ms	10244 KB	Output is correct
6	Correct	156 ms	10248 KB	Output is correct
7	Correct	124 ms	10164 KB	Output is correct
8	Correct	128 ms	10244 KB	Output is correct
9	Correct	125 ms	10132 KB	Output is correct
10	Correct	121 ms	10200 KB	Output is correct
11	Correct	122 ms	10244 KB	Output is correct
12	Correct	123 ms	10356 KB	Output is correct
13	Correct	123 ms	10232 KB	Output is correct
14	Correct	1348 ms	99692 KB	Output is correct
15	Correct	119 ms	10244 KB	Output is correct
16	Correct	1281 ms	99596 KB	Output is correct
17	Correct	1288 ms	99624 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	1 ms	212 KB	Output is correct
2	Correct	12 ms	1236 KB	Output is correct
3	Correct	12 ms	1236 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	300 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 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	212 KB	Output is correct
16	Correct	12 ms	1236 KB	Output is correct
17	Correct	129 ms	10228 KB	Output is correct
18	Incorrect	0 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #785869

Compilation message