oj.uz

답안 #366564

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
366564 2021-02-14T14:11:52 Z Nima_Naderi 이상한 기계 (APIO19_strange_device) C++14
25 / 100
 1161 ms 100596 KB 
///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 1e6 + 10;
const ll INF = 1e18;
ll n, A, B, g, k, m;
ll L[MXN], R[MXN], cnt[MXN];
vector<ll> Num;
vector<pair<ll, ll>> seg;
inline int GetId(ll x){
    return lower_bound(Num.begin(), Num.end(), x) - Num.begin();
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> A >> B;
    g = __gcd(A, B + 1);
    k = (A / g);
    m = (k > (INF + B - 1) / B ? INF + 1 : k * B);
    for(int i = 1; i <= n; i ++){
        cin >> L[i] >> R[i];
        if(R[i] - L[i] + 1 >= m) return cout << m, 0;
        L[i] %= m, R[i] %= m;
        Num.push_back(L[i]), Num.push_back(R[i]), Num.push_back(R[i] + 1);
        if(R[i] < L[i]){
            seg.push_back({L[i], m - 1});
            seg.push_back({0, R[i]});
        }
        else{
            seg.push_back({L[i], R[i]});
        }
    }
    Num.push_back(0), Num.push_back(m - 1);
    Num.push_back(1), Num.push_back(m);
    sort(Num.begin(), Num.end());
    Num.resize(unique(Num.begin(), Num.end()) - Num.begin());
    sort(seg.begin(), seg.end());
    for(auto LR : seg){
        ll l, r; tie(l, r) = LR;
        cnt[GetId(l)] ++, cnt[GetId(r + 1)] --;
    }
    ll ans = 0, bal = 0, len;
    for(int i = 0; i < Num.size() - 1; i ++){
        len = (Num[i + 1] - 1) - Num[i] + 1;
        bal += cnt[i];
        //assert(bal >= 0);
        if(bal) ans += len;
    }
    cout << ans << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 0; i < Num.size() - 1; i ++){
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 9 ms 1256 KB Output is correct
3 Correct 12 ms 1384 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 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 8 ms 1512 KB Output is correct
17 Correct 106 ms 7760 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

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 384 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 478 ms 55524 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 863 ms 63372 KB Output is correct
3 Correct 985 ms 63592 KB Output is correct
4 Correct 810 ms 63596 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 863 ms 63372 KB Output is correct
3 Correct 985 ms 63592 KB Output is correct
4 Correct 810 ms 63596 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 883 ms 100596 KB Output is correct
7 Correct 849 ms 100468 KB Output is correct
8 Correct 928 ms 100524 KB Output is correct
9 Incorrect 1161 ms 100324 KB Output isn't correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 863 ms 63372 KB Output is correct
3 Correct 985 ms 63592 KB Output is correct
4 Correct 810 ms 63596 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 81 ms 11432 KB Output is correct
7 Correct 95 ms 11336 KB Output is correct
8 Correct 81 ms 11336 KB Output is correct
9 Correct 90 ms 11336 KB Output is correct
10 Correct 79 ms 11336 KB Output is correct
11 Correct 89 ms 11388 KB Output is correct
12 Correct 93 ms 11392 KB Output is correct
13 Correct 103 ms 11336 KB Output is correct
14 Correct 81 ms 11476 KB Output is correct
15 Correct 106 ms 11464 KB Output is correct
16 Correct 104 ms 11464 KB Output is correct
17 Correct 87 ms 11336 KB Output is correct
18 Correct 890 ms 100436 KB Output is correct
19 Correct 896 ms 100184 KB Output is correct
20 Incorrect 1104 ms 100448 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 101 ms 8904 KB Output is correct
3 Correct 102 ms 8896 KB Output is correct
4 Incorrect 1137 ms 63516 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 9 ms 1256 KB Output is correct
3 Correct 12 ms 1384 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 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 8 ms 1512 KB Output is correct
17 Correct 106 ms 7760 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 492 KB Output is correct
27 Correct 1 ms 492 KB Output is correct
28 Correct 478 ms 55524 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 863 ms 63372 KB Output is correct
31 Correct 985 ms 63592 KB Output is correct
32 Correct 810 ms 63596 KB Output is correct
33 Correct 1 ms 364 KB Output is correct
34 Correct 883 ms 100596 KB Output is correct
35 Correct 849 ms 100468 KB Output is correct
36 Correct 928 ms 100524 KB Output is correct
37 Incorrect 1161 ms 100324 KB Output isn't correct