oj.uz

답안 #1003735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1003735 2024-06-20T16:32:00 Z underwaterkillerwhale 이상한 기계 (APIO19_strange_device) C++17
65 / 100
 290 ms 51540 KB 
#ifdef ONLINE_JUDGE
    #include "cyberland.h"
#endif

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N  = 1e6 + 7;
const int Mod = 1e9 +7;
const int szBL = 50;
const ll INF = 2e18 + 7;
const int BASE = 137;

int n;
ll A, B;
pair<ll, ll> a[N];


void solution() {
    cin >> n >> A >> B;
    rep (i ,1, n) {
        cin >> a[i].fs >> a[i].se;
    }
    ll K = min((__int128)INF, (__int128)A / __gcd(A, B + 1) * B);
    rep (i, 1, n) {
        if (a[i].se == a[i].fs) {
            a[i].se %= K;
            a[i].fs %= K;
        }
        else {
            a[i].se %= K;
            a[i].fs %= K;
            if (a[i].se <= a[i].fs) {
                a[++n] = {0, a[i].se};
                a[i].se = K - 1;
            }
        }
    }
    sort (a + 1 , a + 1 + n);
    ll mnL = a[1].fs, mxR = a[1].se;
    ll res = 0;
    rep (i, 2, n) {
        if (a[i].fs > mxR) {
            res += mxR - mnL + 1;
            mnL = a[i].fs;
            mxR = a[i].se;
        }
        else {
            mxR = max(mxR, a[i].se);
        }
    }
    res += mxR - mnL + 1;
    cout << res <<"\n";

}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    file ("c");
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}

/*
7
1 2 3 1 2 1 3
1
4 4 30
3
1 1 2 1
0 1 5
0 2 5
1 3 2
2 3 4


3 2
0 1 5
0 2 5
1
1 2

*/

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 3 ms 884 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 352 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 30 ms 5700 KB Output is correct
18 Correct 0 ms 352 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 360 KB Output is correct
2 Incorrect 0 ms 356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 181 ms 40016 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 271 ms 44464 KB Output is correct
3 Correct 290 ms 51024 KB Output is correct
4 Correct 282 ms 51080 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 271 ms 44464 KB Output is correct
3 Correct 290 ms 51024 KB Output is correct
4 Correct 282 ms 51080 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 267 ms 50940 KB Output is correct
7 Correct 251 ms 50968 KB Output is correct
8 Correct 259 ms 51012 KB Output is correct
9 Correct 279 ms 51160 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 271 ms 44464 KB Output is correct
3 Correct 290 ms 51024 KB Output is correct
4 Correct 282 ms 51080 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 31 ms 5720 KB Output is correct
7 Correct 28 ms 5512 KB Output is correct
8 Correct 29 ms 5724 KB Output is correct
9 Correct 27 ms 5692 KB Output is correct
10 Correct 26 ms 5724 KB Output is correct
11 Correct 27 ms 5656 KB Output is correct
12 Correct 26 ms 5716 KB Output is correct
13 Correct 30 ms 5536 KB Output is correct
14 Correct 26 ms 5724 KB Output is correct
15 Correct 28 ms 5724 KB Output is correct
16 Correct 30 ms 5724 KB Output is correct
17 Correct 46 ms 5712 KB Output is correct
18 Correct 257 ms 51156 KB Output is correct
19 Correct 265 ms 50980 KB Output is correct
20 Correct 281 ms 51028 KB Output is correct
21 Correct 32 ms 5712 KB Output is correct
22 Correct 25 ms 5720 KB Output is correct
23 Correct 90 ms 18000 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 28 ms 5104 KB Output is correct
3 Correct 29 ms 5724 KB Output is correct
4 Correct 286 ms 51020 KB Output is correct
5 Correct 28 ms 5556 KB Output is correct
6 Correct 29 ms 5720 KB Output is correct
7 Correct 29 ms 5716 KB Output is correct
8 Correct 30 ms 5712 KB Output is correct
9 Correct 41 ms 5708 KB Output is correct
10 Correct 28 ms 5640 KB Output is correct
11 Correct 28 ms 5716 KB Output is correct
12 Correct 25 ms 5720 KB Output is correct
13 Correct 28 ms 5716 KB Output is correct
14 Correct 274 ms 51332 KB Output is correct
15 Correct 25 ms 5720 KB Output is correct
16 Correct 275 ms 51540 KB Output is correct
17 Correct 251 ms 51284 KB Output is correct
18 Correct 0 ms 344 KB Output is correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 3 ms 884 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 352 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 30 ms 5700 KB Output is correct
18 Correct 0 ms 352 KB Output is correct
19 Correct 0 ms 360 KB Output is correct
20 Incorrect 0 ms 356 KB Output isn't correct
21 Halted 0 ms 0 KB -