Submission #1130197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130197		Hamed_Ghaffari	Strange Device (APIO19_strange_device)	C++20	100 / 100	464 ms	18412 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ull = unsigned long long;

#define X               first
#define Y               second
#define SZ(x)           int(x.size())
#define all(x)          x.begin(), x.end()
#define mins(a,b)       (a = min(a,b))
#define maxs(a,b)       (a = max(a,b))
#define pb              push_back
#define Mp              make_pair
#define lc              id<<1
#define rc              lc|1
#define mid             ((l+r)/2)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = ll(1e18)+23;
const ll  MOD = 1e9 + 7;
const int MXN = 2e5 + 5;
const int LOG = 23;

ll mul(ll a, ll b) { return INF/a<b ? INF : a*b; }

int n;
ll A, B;

void Main() {
    cin >> n >> A >> B;
    ll L = mul(A/gcd(A, B+1), B);
    vector<pll> vc;
    while(n--) {
        ll l, r;
        cin >> l >> r;
        if(r-l+1>=L) {
            cout << L << '\n';
            return;
        }
        l %= L;
        r %= L;
        if(l<=r) vc.pb(Mp(l,r));
        else vc.pb(Mp(l, L-1)), vc.pb(Mp(0, r));
    }
    sort(all(vc));
    vector<pll> ans;
    for(auto [l, r] : vc)
        if(ans.empty() || l>ans.back().Y+1)
            ans.pb(Mp(l, r));
        else
            maxs(ans.back().Y, r);
    ll res=0;
    for(auto [l, r] : ans)
        res += r-l+1;
    cout << res << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--) Main();
    return 0;
}

• 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