Submission #1279018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279018		janson0109	Strange Device (APIO19_strange_device)	C++20	100 / 100	439 ms	49204 KiB

strange_device

#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef __int128 ll;
typedef long double ld;
using namespace std;
const ll M = 998244353;

int main() {
	lol
    long long n, a, b;
    cin >> n >> a >> b;
    vector<pair<long long,long long>> lr(n);
    for(ll i=0; i<n; i++) cin >> lr[i].F >> lr[i].S;
    ll m = ((ll)a)*((ll)b)/((ll)gcd(a, b+1));
    vector<pair<ll,ll>> in;
    for(ll i=0; i<n; i++) {
        if(lr[i].S - lr[i].F >= m - 1) {cout << ((long long) m); return 0;}
        ll d = ((lr[i].S)/m) * m;
        if(d > lr[i].F) {
            in.push_back({lr[i].F % m, m-1});
            in.push_back({0, lr[i].S % m});
        } else in.push_back({lr[i].F % m, lr[i].S % m});
    }
    sort(in.begin(), in.end());
    in.push_back({m, m});
    ll curmx = -1, cur = 0, ans = 0;
    for(auto & x : in) {
        if(x.F > curmx) {
            ans += (curmx - cur + 1);
            curmx = x.S, cur = x.F;
        } else curmx = max(x.S, curmx);
    }
    cout << ((long long)ans);
    
    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