oj.uz

Submission #409654

# Submission time Handle Problem Language Result Execution time Memory
409654 2021-05-21T09:39:34 Z tempus Strange Device (APIO19_strange_device) C++17
5 / 100
 581 ms 51620 KB 
#include <bits/stdc++.h>

#define ll long long
#define endl "\n"
#define ios ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);

using namespace std;

int main() {
    ios
    int n;
    cin >> n;
    ll A, B;
    cin >> A >> B;
    ll S = 0;
    map <ll, ll> was;
    ll l[n], r[n], ans = 0;
    for (int i = 0; i < n; ++ i) {
        cin >> l[i] >> r[i];
        S += r[i] - l[i] + 1;
    }/*
    if (A > 1e18 / B + 1) {
        cout << S;
        return 0;
    }*/
    ll val = A * B / __gcd(B - 1, A);
    vector <pair <ll, ll> > v;
    for (int i = 0; i < n; ++ i) {
        if (l[i] + val <= r[i]) {
            cout << val;
            return 0;
        }
        ll ml = l[i] % val, mr = r[i] % val;
        if (ml <= mr) {
            v.push_back({ml, mr});
        }
        else {
            v.push_back({0, mr});
            v.push_back({ml, val - 1});
        }
    }
    sort(v.begin(), v.end());
    ans = v[0].second - v[0].first + 1;/*
    for (int i = 0; i < v.size(); ++ i) {
        cout << v[i].first << " " << v[i].second << endl;
    }+*/
    for (int i = 1; i < v.size(); ++ i) {
        ll nl = v[i].first, nr = v[i].second;
        if (nl > v[i - 1].second) {
            ans += nr - nl + 1;
            continue;
        }
        else if (nr <= v[i - 1].second) {
            v[i].second = v[i - 1].second;
        }
        else {
            ans += nr - v[i - 1].second;
        }
    }
    cout << ans;
    //3 3 3 4 4 7 9 17 18
    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 1; i < v.size(); ++ i) {
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 844 KB Output is correct
3 Correct 6 ms 1228 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 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 308 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
5.0 / 5.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 378 ms 15944 KB Output isn't correct
3 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 Incorrect 378 ms 15944 KB Output isn't correct
3 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 Incorrect 378 ms 15944 KB Output isn't correct
3 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 53 ms 4040 KB Output is correct
3 Correct 54 ms 7744 KB Output is correct
4 Correct 581 ms 51608 KB Output is correct
5 Correct 53 ms 7724 KB Output is correct
6 Correct 53 ms 7740 KB Output is correct
7 Correct 53 ms 7736 KB Output is correct
8 Correct 54 ms 7744 KB Output is correct
9 Correct 53 ms 7732 KB Output is correct
10 Correct 53 ms 7732 KB Output is correct
11 Correct 57 ms 7732 KB Output is correct
12 Correct 48 ms 7724 KB Output is correct
13 Correct 56 ms 7736 KB Output is correct
14 Correct 558 ms 51620 KB Output is correct
15 Incorrect 67 ms 7720 KB Output isn't correct
16 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 6 ms 844 KB Output is correct
3 Correct 6 ms 1228 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -