Submission #736346

#	Time	Username	Problem	Language	Result	Execution time	Memory
736346		definitelynotmee	Strange Device (APIO19_strange_device)	C++17	15 / 100	471 ms	32604 KiB

strange_device

#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
template <typename T>
using bstring = basic_string<T>;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 998244353;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const ll MAXN = 1e18+10;

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n, a, b;
    cin >> n >> a >> b;

    a/=gcd(b+1,a);

    bool beeg = (MAXN+b-1)/b < a;

    vector<pll> v(n);

    ll resp = 0;
    vector<pll> interval;

    for(auto& [l, r] : v){
        cin >> l >> r;
        if(beeg){
            resp+=r-l+1;
        } else {
            if(r-l >= a*b){
                cout << a*b << '\n';
                return 0;
            }
            ll tl = l%(a*b), tr = r%(a*b);

            if(tl <= tr){
                interval.push_back({tl,tr});
            } else {
                interval.push_back({tl,a*b-1});
                interval.push_back({0,tr});
            }
        }
    }

    if(beeg){
        cout << resp << '\n';
        return 0;
    }

    sort(all(interval));

    ll counted = -1;

    for(auto [l,r] : interval){
        if(counted < l){
            resp+=r-l+1;
            counted = r;
        } else {
            resp+=r-counted;
            counted = r;
        }
    }
    
    cout << resp << '\n';

    return 0;

}

• Subtask 1: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 0 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30