oj.uz

답안 #712920

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
712920 2023-03-20T13:12:03 Z inventiontime 이상한 기계 (APIO19_strange_device) C++17
35 / 100
 678 ms 56208 KB 
#include <bits/stdc++.h>
using namespace std;

#define int ll
#define endl '\n' //comment for interactive
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define pb push_back
#define re resize
#define ff first
#define ss second

#define all(x) (x).begin(), (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)
#define print(x) cout << #x << ": " << x << endl << flush

typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
typedef array<int, 3> ti;
typedef vector<ii> vii;
typedef vector<ti> vti;
typedef priority_queue<int> pq;

template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }

const int inf = 1e17;
//const int maxn = ;

void solve() {

    int n, a, b;
    cin >> n >> a >> b;

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

    vii intvl;
    loop(i, n) {
        int l, r; cin >> l >> r;
        if(r - l + 1 >= p) intvl.pb({0, p-1});
        else {
            int x = l/p;
            l -= x*p;
            r -= x*p;
            if(r >= p) {
                intvl.pb({l, p-1});
                intvl.pb({0, r-p});
            } else {
                intvl.pb({l, r});
            }
        }
    }

    vii pts;
    for(auto [a, b] : intvl) {
        pts.pb({a, 1});
        pts.pb({b, 2});
    }
    sort(all(pts));

    int st = -1;
    int cnt = 0;
    int res = 0;
    for(auto [x, t] : pts) {
        if(t == 1) {
            if(cnt) cnt++;
            else {
                st = x;
                cnt++;
            }
        } else {
            cnt--;
            if(cnt) {}
            else
                res += x - st + 1;
        }
    }

    cout << res << endl;

}

signed main() {

    fast_io;

    int t = 1; //cin >> t;
    while(t--)
        solve();

    return 0;

}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 1492 KB Output is correct
3 Correct 7 ms 1492 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 316 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 320 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 320 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 6 ms 1492 KB Output is correct
17 Correct 65 ms 9752 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 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 1 ms 320 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 411 ms 53596 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 569 ms 56180 KB Output is correct
3 Correct 570 ms 56068 KB Output is correct
4 Correct 548 ms 49892 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 569 ms 56180 KB Output is correct
3 Correct 570 ms 56068 KB Output is correct
4 Correct 548 ms 49892 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 598 ms 49736 KB Output is correct
7 Correct 558 ms 49820 KB Output is correct
8 Correct 563 ms 49856 KB Output is correct
9 Correct 647 ms 49796 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 569 ms 56180 KB Output is correct
3 Correct 570 ms 56068 KB Output is correct
4 Correct 548 ms 49892 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 56 ms 9736 KB Output is correct
7 Correct 57 ms 9808 KB Output is correct
8 Correct 56 ms 9772 KB Output is correct
9 Correct 61 ms 9792 KB Output is correct
10 Correct 53 ms 9752 KB Output is correct
11 Correct 58 ms 9836 KB Output is correct
12 Correct 52 ms 9768 KB Output is correct
13 Correct 61 ms 9796 KB Output is correct
14 Correct 55 ms 9764 KB Output is correct
15 Correct 67 ms 9824 KB Output is correct
16 Correct 65 ms 9800 KB Output is correct
17 Correct 57 ms 9828 KB Output is correct
18 Correct 553 ms 49660 KB Output is correct
19 Correct 545 ms 49708 KB Output is correct
20 Correct 628 ms 49796 KB Output is correct
21 Correct 64 ms 9788 KB Output is correct
22 Correct 54 ms 9780 KB Output is correct
23 Correct 173 ms 34788 KB Output is correct

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 64 ms 9720 KB Output is correct
3 Correct 63 ms 9732 KB Output is correct
4 Correct 678 ms 56208 KB Output is correct
5 Correct 65 ms 9968 KB Output is correct
6 Correct 62 ms 9840 KB Output is correct
7 Correct 62 ms 9796 KB Output is correct
8 Correct 67 ms 9796 KB Output is correct
9 Correct 65 ms 9748 KB Output is correct
10 Correct 62 ms 9764 KB Output is correct
11 Correct 69 ms 9800 KB Output is correct
12 Correct 57 ms 9796 KB Output is correct
13 Correct 62 ms 9796 KB Output is correct
14 Correct 641 ms 55872 KB Output is correct
15 Correct 69 ms 9800 KB Output is correct
16 Correct 525 ms 49908 KB Output is correct
17 Correct 553 ms 49976 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 6 ms 1492 KB Output is correct
3 Correct 7 ms 1492 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 316 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 320 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 320 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 6 ms 1492 KB Output is correct
17 Correct 65 ms 9752 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -