Submission #785875

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
785875	2023-07-17T17:30:50 Z	aykhn	Strange Device (APIO19_strange_device)	C++14	35 / 100	1465 ms	66248 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(1, x));
        }
        else
        {
            int l = a % x + 1;
            int r = b % x + 1;

            if (l <= r)
            {
                s.ins(mpr(l, r));
            }
            else
            {
                s.ins(mpr(l, x));
                s.ins(mpr(1, 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;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	18 ms	940 KB	Output is correct
3	Correct	15 ms	972 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	296 KB	Output is correct
10	Correct	0 ms	300 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	296 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	300 KB	Output is correct
16	Correct	12 ms	952 KB	Output is correct
17	Correct	127 ms	6732 KB	Output is correct
18	Incorrect	1 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	1 ms	212 KB	Output is correct
4	Correct	1 ms	296 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	296 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct
5	Correct	699 ms	420 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	1255 ms	63044 KB	Output is correct
3	Correct	1282 ms	63052 KB	Output is correct
4	Correct	1276 ms	63056 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	1255 ms	63044 KB	Output is correct
3	Correct	1282 ms	63052 KB	Output is correct
4	Correct	1276 ms	63056 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1379 ms	63040 KB	Output is correct
7	Correct	1283 ms	63040 KB	Output is correct
8	Correct	1344 ms	66248 KB	Output is correct
9	Correct	1465 ms	66212 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	1255 ms	63044 KB	Output is correct
3	Correct	1282 ms	63052 KB	Output is correct
4	Correct	1276 ms	63056 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	116 ms	10208 KB	Output is correct
7	Correct	117 ms	10232 KB	Output is correct
8	Correct	117 ms	10196 KB	Output is correct
9	Correct	123 ms	10188 KB	Output is correct
10	Correct	167 ms	10236 KB	Output is correct
11	Correct	143 ms	10260 KB	Output is correct
12	Correct	174 ms	10256 KB	Output is correct
13	Correct	133 ms	10192 KB	Output is correct
14	Correct	116 ms	10248 KB	Output is correct
15	Correct	132 ms	10216 KB	Output is correct
16	Correct	128 ms	10148 KB	Output is correct
17	Correct	124 ms	10180 KB	Output is correct
18	Correct	1345 ms	66164 KB	Output is correct
19	Correct	1361 ms	66008 KB	Output is correct
20	Correct	1426 ms	66068 KB	Output is correct
21	Correct	122 ms	10188 KB	Output is correct
22	Correct	124 ms	10176 KB	Output is correct
23	Correct	334 ms	12808 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	137 ms	10184 KB	Output is correct
3	Correct	135 ms	10188 KB	Output is correct
4	Correct	1371 ms	66024 KB	Output is correct
5	Correct	129 ms	10152 KB	Output is correct
6	Correct	136 ms	10248 KB	Output is correct
7	Correct	128 ms	10252 KB	Output is correct
8	Correct	138 ms	10236 KB	Output is correct
9	Correct	133 ms	10144 KB	Output is correct
10	Correct	123 ms	10232 KB	Output is correct
11	Correct	154 ms	10200 KB	Output is correct
12	Correct	140 ms	10184 KB	Output is correct
13	Correct	134 ms	10192 KB	Output is correct
14	Correct	1333 ms	65812 KB	Output is correct
15	Correct	116 ms	10180 KB	Output is correct
16	Correct	1348 ms	65272 KB	Output is correct
17	Correct	1443 ms	64632 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	1 ms	212 KB	Output is correct
2	Correct	18 ms	940 KB	Output is correct
3	Correct	15 ms	972 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	296 KB	Output is correct
10	Correct	0 ms	300 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	296 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	300 KB	Output is correct
16	Correct	12 ms	952 KB	Output is correct
17	Correct	127 ms	6732 KB	Output is correct
18	Incorrect	1 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #785875

Compilation message