oj.uz

답안 #359369

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
359369 2021-01-27T00:44:00 Z eyangch 이상한 기계 (APIO19_strange_device) C++17
65 / 100
 894 ms 100544 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> s1;

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

void upd(ll l, ll r){
    auto it = s1.upper_bound({l, LLONG_MAX});
    vector<pii> rm;
    if(it != s1.begin()){
        it--;
        if(it -> second >= r){
            return;
        }
        if(it -> second >= l){
            l = it -> first;
            rm.push_back(*it);
        }
        it++;
    }
    for(; it != s1.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){
        s1.erase(i);
    }
    s1.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;
        l %= MOD, r %= MOD;
        if(l > r){
            upd(l, MOD-1);
            upd(0, r);
        }else{
            upd(l, r);
        }
    }
    ll ans = 0;
    for(pii i : s1){
        ans += i.se - i.fi + 1;
    }
    cout << ans << endl;
}

Subtask #1
10.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 1 ms 364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 364 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 78 ms 10348 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 304 ms 364 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 804 ms 63028 KB Output is correct
3 Correct 778 ms 62960 KB Output is correct
4 Correct 894 ms 100352 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 804 ms 63028 KB Output is correct
3 Correct 778 ms 62960 KB Output is correct
4 Correct 894 ms 100352 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 795 ms 100332 KB Output is correct
7 Correct 828 ms 100204 KB Output is correct
8 Correct 782 ms 100272 KB Output is correct
9 Correct 867 ms 100460 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 804 ms 63028 KB Output is correct
3 Correct 778 ms 62960 KB Output is correct
4 Correct 894 ms 100352 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 69 ms 10348 KB Output is correct
7 Correct 68 ms 10348 KB Output is correct
8 Correct 75 ms 10496 KB Output is correct
9 Correct 79 ms 10348 KB Output is correct
10 Correct 76 ms 10348 KB Output is correct
11 Correct 71 ms 10348 KB Output is correct
12 Correct 79 ms 10348 KB Output is correct
13 Correct 105 ms 10348 KB Output is correct
14 Correct 73 ms 10220 KB Output is correct
15 Correct 83 ms 10348 KB Output is correct
16 Correct 85 ms 10348 KB Output is correct
17 Correct 80 ms 10452 KB Output is correct
18 Correct 777 ms 100332 KB Output is correct
19 Correct 818 ms 100544 KB Output is correct
20 Correct 835 ms 100424 KB Output is correct
21 Correct 73 ms 10348 KB Output is correct
22 Correct 85 ms 10476 KB Output is correct
23 Correct 132 ms 12908 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 78 ms 6508 KB Output is correct
3 Correct 79 ms 6636 KB Output is correct
4 Correct 816 ms 63084 KB Output is correct
5 Correct 79 ms 6636 KB Output is correct
6 Correct 79 ms 6636 KB Output is correct
7 Correct 79 ms 6636 KB Output is correct
8 Correct 81 ms 6636 KB Output is correct
9 Correct 77 ms 6636 KB Output is correct
10 Correct 71 ms 6636 KB Output is correct
11 Correct 73 ms 6636 KB Output is correct
12 Correct 76 ms 6636 KB Output is correct
13 Correct 80 ms 6636 KB Output is correct
14 Correct 886 ms 63080 KB Output is correct
15 Correct 70 ms 5996 KB Output is correct
16 Correct 784 ms 100204 KB Output is correct
17 Correct 785 ms 100332 KB Output is correct
18 Correct 1 ms 364 KB Output is 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 1 ms 364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 364 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 78 ms 10348 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 0 ms 364 KB Output is correct
20 Incorrect 0 ms 364 KB Output isn't correct
21 Halted 0 ms 0 KB -