oj.uz

답안 #785875

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

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

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

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

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

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

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

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

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