Submission #1200101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200101		adiyer	Strange Device (APIO19_strange_device)	C++20	20 / 100	634 ms	432108 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 11;

ll n, a, b, c, res, sz = 1;
ll l[N], r[N], was[N], t[20 * N];

int lv[30 * N], rv[30 * N], lzy[30 * N];

__int128 val;

void push(ll v, ll l, ll r){
    if(lzy[v] == 0) return; 
    if(l != r){
        if(!lv[v]) lv[v] = ++sz;
        if(!rv[v]) rv[v] = ++sz;
        lzy[lv[v]] = lzy[rv[v]] = 1;
    }
    t[v] = (r - l + 1);
}

void upd(ll tl, ll tr, ll x, ll v = 1, ll l = 0, ll r = c - 1){
    push(v, l, r);
    if(r < tl || tr < l) return;
    if(tl <= l && r <= tr){
        lzy[v] = 1, push(v, l, r);
        return;
    }
    ll md = (l + r) / 2;
    if(!lv[v]) lv[v] = ++sz;
    if(!rv[v]) rv[v] = ++sz;
    upd(tl, tr, x, lv[v], l, md);
    upd(tl, tr, x, rv[v], md + 1, r);
    t[v] = t[lv[v]] + t[rv[v]];
}

void solve(){
    cin >> n >> a >> b;
    for(ll i = 1; i <= n; i++) cin >> l[i] >> r[i]; 
    val = a / __gcd(a, b + 1), val *= b;
    if(val > 1e18){
        for(ll i = 1; i <= n; i++) res += r[i] - l[i] + 1;
        cout << res;
        return;
    }
    c = val;
    for(ll i = 1; i <= n; i++){
        if(r[i] - l[i] + 1 >= c){
            cout << c << '\n';
            return;
        }
        l[i] %= c, r[i] %= c;
        if(l[i] <= r[i]) upd(l[i], r[i], 1);
        else upd(l[i], c - 1, 1), upd(0, r[i], 1);
    }
    cout << t[1];
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt--) solve();
}

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