oj.uz

Submission #366563

# Submission time Handle Problem Language Result Execution time Memory
366563 2021-02-14T14:11:11 Z Nima_Naderi Strange Device (APIO19_strange_device) C++14
0 / 100
 857 ms 63560 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 9 ms 1384 KB Output isn't correct
3 Halted 0 ms 0 KB -

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 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Incorrect 1 ms 492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 857 ms 63560 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 857 ms 63560 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 857 ms 63560 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 102 ms 7948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 9 ms 1384 KB Output isn't correct
3 Halted 0 ms 0 KB -