oj.uz

답안 #785869

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
785869 2023-07-17T17:15:36 Z aykhn 이상한 기계 (APIO19_strange_device) C++14
35 / 100
 1357 ms 100012 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -