oj.uz

Submission #382937

# Submission time Handle Problem Language Result Execution time Memory
382937 2021-03-28T14:46:58 Z abil Strange Device (APIO19_strange_device) C++14
30 / 100
 725 ms 80108 KB 
#include <bits/stdc++.h>

#define SPEEDUP ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(),s.end()
#define int long long

using namespace std;

const int N = (1e6 + 12);
const int mod = (1e9 + 7);
const int inf = (1e18 + 7);

int l[N], r[N];

main(){
    SPEEDUP;
    int n, A, B;
    cin >> n >> A >> B;
//    for(int i = 1; i <= 25; i++){
//        cout << i << " ";
//    }
//    cout << endl;
//    vector<int > vec;
//    for(int i = 0;i <= 25; i++){
//        cout << ((i + (i + B - 1) / B)) << " ";
//        vec.pb(((i + (i + B - 1) / B)));
//    }
//    cout << endl;
//    for(int i = 0;i <= 30; i++){
//        cout << (i % B) << " ";
//    }
//    cout << endl;
//    for(auto to : vec){
//        cout << to % A << " ";
//    }
//    cout << endl;

    for(int i = 1; i <= n; i++){
        cin >> l[i] >> r[i];
    }
    int ans = 0;
    int la = -1, ra = -1;
    for(int i = 1; i <= n; i++){
        if(la == -1){
            la = l[i], ra = r[i];
        }
        else{
            la = max(la, l[i]);
            ra = max(ra, r[i]);
        }
        ans += ra - la + 1;
        la = ra + 1;
    }
    int x;
    if(0 == (A % (B + 1ll))){
        if(inf / B >= (A / (B + 1ll))){
            x = B * (A / (B + 1ll));
        }
        else{
            cout << ans << endl;
            return 0;
        }
    }
    else{
        if(inf / A >= B){
            x = A * B;
        }
        else{
            cout << ans << endl;
            return 0;
        }
    }
    set<pair<int,int >> st;
    for(int i = 1;i <= n; i++){
        if(r[i] % x >= l[i] % x){
//            cout << i << " ! " << l[i] % x << " " << r[i] % x <<endl;
            st.insert({l[i] % x, r[i] % x});
        }
        else{
//            cout << i << " ? " << 0 << " " << r[i] % x << endl;
//            cout << i << " ? " << l[i] % x << " " << x - 1 << endl;
            st.insert({0, r[i] % x});
            st.insert({l[i] % x, x - 1});
        }
    }
    ans = 0;
    la = -1, ra = -1;
    for(auto to : st){
        if(la == -1){
            la = to.fr, ra = to.sc;
        }
        else{
            la = max(la, to.fr);
            ra = max(ra, to.sc);
        }
        ans += ra - la + 1;
        la = ra + 1;
    }
    cout << ans;
}

Compilation message

strange_device.cpp:19:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   19 | main(){
      |      ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 1132 KB Output is correct
3 Correct 7 ms 1516 KB Output is correct
4 Incorrect 1 ms 384 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 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 304 ms 16620 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 662 ms 78676 KB Output is correct
3 Correct 678 ms 79084 KB Output is correct
4 Correct 674 ms 79176 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 662 ms 78676 KB Output is correct
3 Correct 678 ms 79084 KB Output is correct
4 Correct 674 ms 79176 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 722 ms 79036 KB Output is correct
7 Correct 661 ms 79348 KB Output is correct
8 Correct 707 ms 80108 KB Output is correct
9 Incorrect 718 ms 79596 KB Output isn't correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 662 ms 78676 KB Output is correct
3 Correct 678 ms 79084 KB Output is correct
4 Correct 674 ms 79176 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 62 ms 9072 KB Output is correct
7 Correct 63 ms 9068 KB Output is correct
8 Correct 62 ms 9196 KB Output is correct
9 Correct 71 ms 9068 KB Output is correct
10 Correct 62 ms 9068 KB Output is correct
11 Correct 61 ms 9068 KB Output is correct
12 Correct 62 ms 9068 KB Output is correct
13 Correct 81 ms 9068 KB Output is correct
14 Correct 62 ms 9196 KB Output is correct
15 Correct 67 ms 9068 KB Output is correct
16 Correct 69 ms 9068 KB Output is correct
17 Correct 64 ms 9068 KB Output is correct
18 Correct 656 ms 79596 KB Output is correct
19 Correct 675 ms 79724 KB Output is correct
20 Correct 725 ms 79636 KB Output is correct
21 Correct 62 ms 9068 KB Output is correct
22 Correct 63 ms 9068 KB Output is correct
23 Correct 150 ms 8684 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 66 ms 8136 KB Output is correct
3 Correct 67 ms 9068 KB Output is correct
4 Correct 684 ms 79596 KB Output is correct
5 Correct 65 ms 8428 KB Output is correct
6 Correct 65 ms 8428 KB Output is correct
7 Correct 65 ms 8556 KB Output is correct
8 Correct 71 ms 8540 KB Output is correct
9 Correct 64 ms 8428 KB Output is correct
10 Correct 62 ms 8488 KB Output is correct
11 Correct 67 ms 8556 KB Output is correct
12 Correct 67 ms 8480 KB Output is correct
13 Correct 64 ms 8428 KB Output is correct
14 Correct 683 ms 78956 KB Output is correct
15 Incorrect 70 ms 8428 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 364 KB Output is correct
2 Correct 7 ms 1132 KB Output is correct
3 Correct 7 ms 1516 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -