oj.uz

Submission #359376

# Submission time Handle Problem Language Result Execution time Memory
359376 2021-01-27T00:51:50 Z eyangch Strange Device (APIO19_strange_device) C++17
35 / 100
 897 ms 63400 KB 
#include <bits/stdc++.h>
#define endl "\n"
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

int N;
ll A, B, MOD;
set<pii> s;

ll gcdf(ll a, ll b){
    return (b == 0 ? a : gcdf(b, a%b));
}

void upd(ll l, ll r){
    auto it = s.upper_bound({l, LLONG_MAX});
    vector<pii> rm;
    if(it != s.begin()){
        it--;
        if(it -> second >= r){
            return;
        }
        if(it -> second >= l){
            l = it -> first;
            rm.push_back(*it);
        }
        it++;
    }
    for(; it != s.end(); it++){
        if(it -> first > r) break;
        l = min(l, it -> first);
        r = max(r, it -> second);
        rm.push_back(*it);
    }
    for(pii i : rm){
        s.erase(i);
    }
    s.insert({l, r});
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> A >> B;
    __int128 mp = A / gcdf(A, B+1) * B;
    MOD = (mp > 1e18 ? 1e18+1 : (ll)mp);
    for(int i = 0; i < N; i++){
        ll l, r; cin >> l >> r;
        if(r - l + 1 >= MOD){
            upd(0, MOD-1);
            break;
        }
        l %= MOD, r %= MOD;
        if(l > r){
            upd(l, MOD-1);
            upd(0, r);
        }else{
            upd(l, r);
        }
    }
    ll ans = 0;
    for(pii i : s){
        ans += i.se - i.fi + 1;
    }
    cout << ans << endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 1260 KB Output is correct
3 Correct 8 ms 1260 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 7 ms 1260 KB Output is correct
17 Correct 75 ms 7276 KB Output is correct
18 Incorrect 1 ms 364 KB Output isn't correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory 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 315 ms 364 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 822 ms 63400 KB Output is correct
3 Correct 799 ms 62968 KB Output is correct
4 Correct 897 ms 63072 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 822 ms 63400 KB Output is correct
3 Correct 799 ms 62968 KB Output is correct
4 Correct 897 ms 63072 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 802 ms 63096 KB Output is correct
7 Correct 885 ms 62944 KB Output is correct
8 Correct 778 ms 63016 KB Output is correct
9 Correct 861 ms 62956 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 822 ms 63400 KB Output is correct
3 Correct 799 ms 62968 KB Output is correct
4 Correct 897 ms 63072 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 78 ms 7148 KB Output is correct
7 Correct 68 ms 7148 KB Output is correct
8 Correct 78 ms 7276 KB Output is correct
9 Correct 77 ms 7276 KB Output is correct
10 Correct 90 ms 7184 KB Output is correct
11 Correct 69 ms 7276 KB Output is correct
12 Correct 77 ms 7276 KB Output is correct
13 Correct 78 ms 7276 KB Output is correct
14 Correct 76 ms 7148 KB Output is correct
15 Correct 81 ms 7276 KB Output is correct
16 Correct 81 ms 7276 KB Output is correct
17 Correct 86 ms 7316 KB Output is correct
18 Correct 788 ms 63340 KB Output is correct
19 Correct 812 ms 63084 KB Output is correct
20 Correct 834 ms 63040 KB Output is correct
21 Correct 71 ms 7248 KB Output is correct
22 Correct 86 ms 7276 KB Output is correct
23 Correct 131 ms 784 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 91 ms 7148 KB Output is correct
3 Correct 83 ms 7276 KB Output is correct
4 Correct 843 ms 63060 KB Output is correct
5 Correct 90 ms 7276 KB Output is correct
6 Correct 82 ms 7268 KB Output is correct
7 Correct 81 ms 7276 KB Output is correct
8 Correct 79 ms 7276 KB Output is correct
9 Correct 76 ms 7292 KB Output is correct
10 Correct 70 ms 7276 KB Output is correct
11 Correct 73 ms 7276 KB Output is correct
12 Correct 79 ms 7404 KB Output is correct
13 Correct 79 ms 7276 KB Output is correct
14 Correct 848 ms 63048 KB Output is correct
15 Correct 65 ms 6636 KB Output is correct
16 Correct 765 ms 62984 KB Output is correct
17 Correct 780 ms 62956 KB Output is correct
18 Incorrect 1 ms 364 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 1260 KB Output is correct
3 Correct 8 ms 1260 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 7 ms 1260 KB Output is correct
17 Correct 75 ms 7276 KB Output is correct
18 Incorrect 1 ms 364 KB Output isn't correct