Submission #366565

#	Time	Username	Problem	Language	Result	Execution time	Memory
366565		Nima_Naderi	Strange Device (APIO19_strange_device)	C++14	100 / 100	1161 ms	108528 KiB

strange_device

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 4e6 + 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 > 0) 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 (stderr)

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 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30