oj.uz

답안 #359393

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
359393 2021-01-27T01:05:06 Z eyangch 이상한 기계 (APIO19_strange_device) C++17
35 / 100
 892 ms 63340 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+5 : (ll)mp);
    for(int i = 0; i < N; i++){
        ll l, r; cin >> l >> r;
        if(r - l + 1 >= MOD){
            upd(0, MOD-1);
        }
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 1004 KB Output is correct
3 Correct 7 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 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 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 0 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 876 KB Output is correct
17 Correct 76 ms 6636 KB Output is correct
18 Incorrect 0 ms 364 KB Output isn't correct

Subtask #2
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 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Incorrect 0 ms 364 KB Output isn't correct

Subtask #3
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 307 ms 492 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 793 ms 63084 KB Output is correct
3 Correct 784 ms 63084 KB Output is correct
4 Correct 872 ms 63084 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 793 ms 63084 KB Output is correct
3 Correct 784 ms 63084 KB Output is correct
4 Correct 872 ms 63084 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 787 ms 63204 KB Output is correct
7 Correct 799 ms 63340 KB Output is correct
8 Correct 773 ms 63028 KB Output is correct
9 Correct 892 ms 63144 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 793 ms 63084 KB Output is correct
3 Correct 784 ms 63084 KB Output is correct
4 Correct 872 ms 63084 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 66 ms 6508 KB Output is correct
7 Correct 72 ms 6636 KB Output is correct
8 Correct 69 ms 6636 KB Output is correct
9 Correct 76 ms 6636 KB Output is correct
10 Correct 78 ms 6508 KB Output is correct
11 Correct 68 ms 6636 KB Output is correct
12 Correct 88 ms 6528 KB Output is correct
13 Correct 78 ms 6636 KB Output is correct
14 Correct 71 ms 6508 KB Output is correct
15 Correct 88 ms 6764 KB Output is correct
16 Correct 78 ms 6636 KB Output is correct
17 Correct 79 ms 6636 KB Output is correct
18 Correct 788 ms 63212 KB Output is correct
19 Correct 795 ms 63000 KB Output is correct
20 Correct 822 ms 63084 KB Output is correct
21 Correct 72 ms 6636 KB Output is correct
22 Correct 79 ms 6636 KB Output is correct
23 Correct 128 ms 364 KB Output is correct

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 75 ms 6508 KB Output is correct
3 Correct 93 ms 6636 KB Output is correct
4 Correct 810 ms 62956 KB Output is correct
5 Correct 79 ms 6636 KB Output is correct
6 Correct 81 ms 6764 KB Output is correct
7 Correct 80 ms 6636 KB Output is correct
8 Correct 78 ms 6636 KB Output is correct
9 Correct 80 ms 6636 KB Output is correct
10 Correct 71 ms 6636 KB Output is correct
11 Correct 72 ms 6636 KB Output is correct
12 Correct 76 ms 6636 KB Output is correct
13 Correct 78 ms 6764 KB Output is correct
14 Correct 858 ms 62952 KB Output is correct
15 Correct 66 ms 5996 KB Output is correct
16 Correct 777 ms 63084 KB Output is correct
17 Correct 769 ms 62956 KB Output is correct
18 Incorrect 1 ms 364 KB Output isn't correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 1004 KB Output is correct
3 Correct 7 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 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 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 0 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 876 KB Output is correct
17 Correct 76 ms 6636 KB Output is correct
18 Incorrect 0 ms 364 KB Output isn't correct