oj.uz

Submission #398444

# Submission time Handle Problem Language Result Execution time Memory
398444 2021-05-04T09:45:03 Z AKiko Strange Device (APIO19_strange_device) C++17
5 / 100
 1848 ms 79604 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ss second
#define ff first
#define pb push_back
#define pii pair<int, int>
#define INF INT64_MAX
#define debug(n) cout << #n << " = " << n << "\n";
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll MOD = 1e9 + 7;

int main() {
    ll n, A, B, T, K;
    cin >> n >> A >> B;
    K = A / __gcd(B + 1, A);
    if(INF / A / B > 0) {
        T = K * B;
    } else {
        T = INF;
    }
    map<ll, ll> m;
    for(int i = 0; i < n; i++) {
        ll l, r;
        cin >> l >> r;
        if(r - l + 1 >= T) {
            cout << T << "\n";
            return 0;
        }
        if(r % T < l % T) {
            m[0]++;
            m[r % T + 1]--;
            m[l]++;
            m[T]--;
        } else {
            m[l % T]++;
            m[r % T + 1]--;
        }
    }
    ll prev = 0;
    vector<pair<ll, ll> > segments;
    for(auto el : m) {
        prev += el.ss;
        segments.pb({el.ff, prev});
    }

    ll ans = 0;
    for(int i = 0; i < int(segments.size() - 1); i++) {
        if(segments[i].ss > 0){
            ans += segments[i + 1].ff - segments[i].ff;
        }
    }

    cout << ans << "\n";
    /*
    (x, y) = ((t + t / B) % A, t % B)
    (x, y) = (((t + T) + (t + T) / B) % A, (t + T) % B);
    T = BK
    x = (t + t / B) % A
    x = ((t + T) + (t + T) / B) % A
    0 = (BK + K) % A;
    0 = K(B + 1) % A;
    */

    return 0;
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 18 ms 1332 KB Output is correct
3 Incorrect 17 ms 1248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1809 ms 79584 KB Output is correct
3 Incorrect 1848 ms 79604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1809 ms 79584 KB Output is correct
3 Incorrect 1848 ms 79604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1809 ms 79584 KB Output is correct
3 Incorrect 1848 ms 79604 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 204 KB Output is correct
2 Correct 193 ms 8688 KB Output is correct
3 Correct 184 ms 8676 KB Output is correct
4 Correct 1840 ms 79556 KB Output is correct
5 Correct 180 ms 8752 KB Output is correct
6 Correct 221 ms 8624 KB Output is correct
7 Correct 180 ms 8660 KB Output is correct
8 Correct 181 ms 8692 KB Output is correct
9 Correct 199 ms 8764 KB Output is correct
10 Correct 175 ms 8708 KB Output is correct
11 Correct 177 ms 8728 KB Output is correct
12 Incorrect 188 ms 8660 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 18 ms 1332 KB Output is correct
3 Incorrect 17 ms 1248 KB Output isn't correct
4 Halted 0 ms 0 KB -