oj.uz

Submission #398439

# Submission time Handle Problem Language Result Execution time Memory
398439 2021-05-04T09:31:49 Z AKiko Strange Device (APIO19_strange_device) C++17
0 / 100
 1850 ms 81164 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 INT_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);
    T = K * B;
    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";

    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 1232 KB Output is correct
3 Incorrect 20 ms 1232 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 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 Incorrect 1 ms 204 KB Output isn't correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 2 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 204 KB Output is correct
2 Correct 1850 ms 79356 KB Output is correct
3 Incorrect 1832 ms 79572 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 204 KB Output is correct
2 Correct 1850 ms 79356 KB Output is correct
3 Incorrect 1832 ms 79572 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 204 KB Output is correct
2 Correct 1850 ms 79356 KB Output is correct
3 Incorrect 1832 ms 79572 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 185 ms 8712 KB Output is correct
3 Correct 180 ms 8664 KB Output is correct
4 Correct 1849 ms 81164 KB Output is correct
5 Correct 194 ms 8632 KB Output is correct
6 Correct 182 ms 8716 KB Output is correct
7 Correct 180 ms 8760 KB Output is correct
8 Correct 178 ms 8700 KB Output is correct
9 Correct 194 ms 8724 KB Output is correct
10 Correct 179 ms 8788 KB Output is correct
11 Correct 176 ms 8640 KB Output is correct
12 Incorrect 181 ms 8928 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 1232 KB Output is correct
3 Incorrect 20 ms 1232 KB Output isn't correct
4 Halted 0 ms 0 KB -