oj.uz

Submission #1003669

# Submission time Handle Problem Language Result Execution time Memory
1003669 2024-06-20T14:57:41 Z underwaterkillerwhale Strange Device (APIO19_strange_device) C++17
0 / 100
 445 ms 35060 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  = 5e5 + 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, 20) cout << i<<":"<<(i + i / B) %  A <<" "<<i % B <<"\n";
    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);
//    rep (i,1, n) cout << a[i].fs <<" "<<a[i].se <<"\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 3 ms 1116 KB Output is correct
3 Incorrect 4 ms 856 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 0 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 348 KB Output is correct
2 Runtime error 445 ms 35052 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 445 ms 35052 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 445 ms 35052 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 30 ms 6264 KB Output is correct
3 Correct 27 ms 6236 KB Output is correct
4 Runtime error 104 ms 35060 KB Execution killed with signal 11
5 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 3 ms 1116 KB Output is correct
3 Incorrect 4 ms 856 KB Output isn't correct
4 Halted 0 ms 0 KB -