oj.uz

Submission #568695

# Submission time Handle Problem Language Result Execution time Memory
568695 2022-05-26T05:28:51 Z joshjms Strange Device (APIO19_strange_device) C++14
10 / 100
 773 ms 49040 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << "\n";

const long long mod = 1e9 + 7;
const long long MAX = 1e18;

int n, a, b, L[1000005], R[1000005], s, m;
vector <pair<int,int>> ls;
int cnt, prv, ans;

void solve () {
    cin >> n >> a >> b;

    for(int i = 1; i <= n; i++) {
        cin >> L[i] >> R[i];
        s += R[i] - L[i] + 1;
    }

    if(MAX / a < b) {
        cout << s << "\n";
        return;
    }

    m = a * b;

    for(int i = 1; i <= n; i++) {
        if(R[i] - L[i] + 1 >= m) {
            cout << m << "\n";
            return;
        }
    }

    for(int i = 1; i <= n; i++) {
        L[i] %= m;
        R[i] %= m;

        if(R[i] < L[i]) {
            ls.pb({L[i], 0});
            ls.pb({m, 1});
            ls.pb({0, 0});
            ls.pb({R[i] + 1, 1});
        }
        else {
            ls.pb({L[i], 0});
            ls.pb({R[i] + 1, 1});
        }
    }
    
    sort(ls.begin(), ls.end());
    cnt = 0, prv = -1;

    // for(auto i : ls) cout << i.fi << " ";
    // cout << "\n";

    for(int i = 0; i < ls.size(); i++) {
        if(ls[i].se == 0) cnt++;
        else cnt--;

        if(i < ls.size() - 1 && ls[i].fi == ls[i + 1].fi) continue;

        if(cnt > 0 && prv == -1) {prv = ls[i].fi;}
        if(cnt == 0 && prv != -1) {ans += ls[i].fi - prv; prv = -1;}
    }

    cout << ans << "\n";

}

signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Compilation message

strange_device.cpp: In function 'void solve()':
strange_device.cpp:62:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < ls.size(); i++) {
      |                    ~~^~~~~~~~~~~
strange_device.cpp:66:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if(i < ls.size() - 1 && ls[i].fi == ls[i + 1].fi) continue;
      |            ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 5 ms 1112 KB Output is correct
3 Correct 5 ms 1112 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 374 ms 48956 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 550 ms 49040 KB Output is correct
3 Incorrect 606 ms 48932 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 212 KB Output is correct
2 Correct 550 ms 49040 KB Output is correct
3 Incorrect 606 ms 48932 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 212 KB Output is correct
2 Correct 550 ms 49040 KB Output is correct
3 Incorrect 606 ms 48932 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 212 KB Output is correct
2 Correct 67 ms 6080 KB Output is correct
3 Correct 78 ms 6088 KB Output is correct
4 Correct 773 ms 48952 KB Output is correct
5 Correct 56 ms 6072 KB Output is correct
6 Correct 58 ms 6060 KB Output is correct
7 Correct 67 ms 6064 KB Output is correct
8 Correct 58 ms 6060 KB Output is correct
9 Correct 54 ms 6092 KB Output is correct
10 Correct 65 ms 6092 KB Output is correct
11 Correct 56 ms 6080 KB Output is correct
12 Correct 51 ms 6080 KB Output is correct
13 Correct 57 ms 6048 KB Output is correct
14 Correct 608 ms 48908 KB Output is correct
15 Incorrect 58 ms 6060 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 212 KB Output is correct
2 Correct 5 ms 1112 KB Output is correct
3 Correct 5 ms 1112 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -