oj.uz

Submission #1003672

# Submission time Handle Problem Language Result Execution time Memory
1003672 2024-06-20T14:59:04 Z underwaterkillerwhale Strange Device (APIO19_strange_device) C++17
0 / 100
 294 ms 53116 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 = 1e18 + 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; {
        if (A > INF / B)
            K = INF;
        else K = A * B;
    }
    bool ok = 0;
    rep (i, 1, n) {
        a[i].fs %= K;
        a[i].se %= K;
        if (a[i].se < a[i].fs) {
            a[i].se = K - 1;
            ok = 1;
        }
    }
    if (ok) a[++n] = {0, 0};
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 10 ms 604 KB Output is correct
3 Incorrect 3 ms 624 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 250 ms 34432 KB Output is correct
3 Incorrect 250 ms 53116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 250 ms 34432 KB Output is correct
3 Incorrect 250 ms 53116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 250 ms 34432 KB Output is correct
3 Incorrect 250 ms 53116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 26 ms 2700 KB Output is correct
3 Correct 27 ms 2652 KB Output is correct
4 Correct 294 ms 34388 KB Output is correct
5 Correct 29 ms 6236 KB Output is correct
6 Correct 29 ms 6228 KB Output is correct
7 Correct 28 ms 6228 KB Output is correct
8 Correct 28 ms 6228 KB Output is correct
9 Correct 36 ms 6380 KB Output is correct
10 Correct 31 ms 6224 KB Output is correct
11 Correct 36 ms 6204 KB Output is correct
12 Incorrect 25 ms 6224 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 10 ms 604 KB Output is correct
3 Incorrect 3 ms 624 KB Output isn't correct
4 Halted 0 ms 0 KB -