oj.uz

답안 #382951

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
382951 2021-03-28T15:26:14 Z abil 이상한 기계 (APIO19_strange_device) C++14
35 / 100
 741 ms 78804 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 = 0; 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 <= 25; 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(x <= r[i] - l[i] + 1){
            cout << x << endl;
            return 0;
        }
        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);
        }
        if(la <= ra){
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 7 ms 1132 KB Output is correct
3 Correct 7 ms 1132 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 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 492 KB Output is correct
5 Correct 303 ms 16108 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 649 ms 78628 KB Output is correct
3 Correct 662 ms 78732 KB Output is correct
4 Correct 658 ms 78572 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 649 ms 78628 KB Output is correct
3 Correct 662 ms 78732 KB Output is correct
4 Correct 658 ms 78572 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 672 ms 78572 KB Output is correct
7 Correct 709 ms 78740 KB Output is correct
8 Correct 647 ms 78624 KB Output is correct
9 Incorrect 670 ms 78744 KB Output isn't correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 649 ms 78628 KB Output is correct
3 Correct 662 ms 78732 KB Output is correct
4 Correct 658 ms 78572 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 81 ms 8172 KB Output is correct
7 Correct 62 ms 8172 KB Output is correct
8 Correct 61 ms 8172 KB Output is correct
9 Correct 70 ms 8172 KB Output is correct
10 Correct 69 ms 8300 KB Output is correct
11 Correct 60 ms 8172 KB Output is correct
12 Correct 62 ms 8192 KB Output is correct
13 Correct 65 ms 8172 KB Output is correct
14 Correct 61 ms 8172 KB Output is correct
15 Correct 65 ms 8320 KB Output is correct
16 Correct 65 ms 8172 KB Output is correct
17 Correct 62 ms 8200 KB Output is correct
18 Correct 694 ms 78608 KB Output is correct
19 Correct 654 ms 78804 KB Output is correct
20 Correct 741 ms 78572 KB Output is correct
21 Correct 67 ms 8172 KB Output is correct
22 Correct 65 ms 8172 KB Output is correct
23 Correct 131 ms 5740 KB Output is correct

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 64 ms 8556 KB Output is correct
3 Correct 66 ms 8172 KB Output is correct
4 Correct 678 ms 78700 KB Output is correct
5 Correct 63 ms 8172 KB Output is correct
6 Correct 65 ms 8172 KB Output is correct
7 Correct 64 ms 8172 KB Output is correct
8 Correct 70 ms 8172 KB Output is correct
9 Correct 64 ms 8172 KB Output is correct
10 Correct 62 ms 8172 KB Output is correct
11 Correct 63 ms 8300 KB Output is correct
12 Correct 62 ms 8172 KB Output is correct
13 Correct 64 ms 8172 KB Output is correct
14 Correct 678 ms 78592 KB Output is correct
15 Incorrect 64 ms 8172 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 7 ms 1132 KB Output is correct
3 Correct 7 ms 1132 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -