Submission #781542

#	Time	Username	Problem	Language	Result	Execution time	Memory
781542		devariaota	Strange Device (APIO19_strange_device)	C++17	100 / 100	453 ms	93420 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second

ll l[1000005], r[1000005];
vector<pair<ll, ll>> v, ans;

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    /*
    t = xb;
    xb + x = y * a
    x * (b + 1) = y * a
    x = lcm(b + 1, a) / (b + 1)
    a/gcd(b + 1, a) = lcm(b + 1, a) / (b + 1);
    x = a/gcd(b + 1, a)
    banyaknya possibility = x * b -> x = a / gcd(b + 1, a);
    x * b >= r
    b / x
    */
    int n;
    ll a, b;
    cin >> n >> a >> b;
    ll x = a / gcd(b + 1, a), sum = 0, ans1 = 0;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        sum += r[i] - l[i] + 1;
    }
    if ((r[n] - 1) / x < b) {
        cout << sum << "\n";
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        if (r[i] - l[i] + 1 >= x * b) {
            cout << x * b;
            return 0;
        }
        l[i] %= (x * b), r[i] %= (x * b);
        if (l[i] <= r[i]) v.push_back({l[i], r[i]});
        else v.push_back({l[i], x * b - 1}), v.push_back({0, r[i]});
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < (int)v.size(); i++) {
        if (ans.empty()) {
            ans.push_back(v[i]);
            continue;
        }
        if (v[i].fi > ans.back().se) ans.push_back(v[i]);
        else ans.back().se = max(ans.back().se, v[i].se);
    }  
    for (auto u : ans) ans1 += u.se - u.fi + 1;
    cout << ans1 << "\n";
} 

• 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