Submission #1146264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146264		vladilius	Strange Device (APIO19_strange_device)	C++20	40 / 100	1752 ms	589824 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define arr4 array<ll, 4>

struct ST{
    struct node{
        int l, r;
        int m; ll c, p;
        node(ll x){
            l = r = m = p = 0;
            c = x;
        }
    };
    vector<node> all;
    ll n;
    ST(ll ns){
        n = ns;
        all.pb(node(0));
        all.pb(node(n));
    }
    void push(int v){
        if (!all[v].p) return;
        all[all[v].l].m += all[v].p;
        all[all[v].r].m += all[v].p;
        all[all[v].l].p += all[v].p;
        all[all[v].r].p += all[v].p;
        all[v].p = 0;
    }
    int nw(ll x){
        all.pb(node(x));
        return (int) all.size() - 1;
    }
    void add(int v, ll tl, ll tr, ll l, ll r, int x){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            all[v].m += x;
            all[v].p += x;
            return;
        }
        ll tm = (tl + tr) / 2;
        if (!all[v].l) all[v].l = nw(tm - tl + 1);
        if (!all[v].r) all[v].r = nw(tr - tm);
        push(v);
        add(all[v].l, tl, tm, l, r, x);
        add(all[v].r, tm + 1, tr, l, r, x);
        all[v].m = min(all[all[v].l].m, all[all[v].r].m);
        all[v].c = 0;
        if (all[all[v].l].m == all[v].m) all[v].c += all[all[v].l].c;
        if (all[all[v].r].m == all[v].m) all[v].c += all[all[v].r].c;
    };
    void add(ll l, ll r, int x){
        add(1, 1, n, l, r, x);
    }
    ll get(){
        ll out = n;
        if (!all[1].m) out -= all[1].c;
        return out;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; ll a, b; cin>>n>>a>>b;
    vector<ll> l(n + 1), r(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>l[i]>>r[i];
    }
    
    vector<arr4> all;
    
    a /= gcd(a, b + 1);
    for (int i = 1; i <= n; i++){
        ll r1 = r[i] % b, r2 = l[i] % b - 1;
        if (r2 == -1) r2 += b;
        
        if (r1 > r2) swap(r1, r2);

        vector<pll> f;
        if ((r[i] - l[i] + 1) >= b) f.pb({0, b - 1});
        else {
            ll x = l[i] % b, y = r[i] % b;
            if (x <= y){
                f.pb({x, y});
            }
            else {
                f.pb({x, b - 1});
                f.pb({0, y});
            }
        }
        
        vector<arr4> pos;
        
        ll L = ceil((long double) l[i] / b), R = r[i] / b;
        pos.pb({0, r1, L, R});
        
        L = ceil((long double) (l[i] - r2) / b); R = (r[i] - r2) / b;
        if (r1 + 1 <= r2) pos.pb({r1 + 1, r2, L, R});
      
        L = ceil((long double) (l[i] - (r2 + 1)) / b); R = (r[i] - (r2 + 1)) / b;
        if (r2 + 1 <= b - 1) pos.pb({r2 + 1, b - 1, L, R});
        
        for (auto [l1, r1, L, R]: pos){
            for (auto [l2, r2]: f){
                ll l3 = max(l1, l2), r3 = min(r1, r2);
                if (l3 <= r3){
                    all.pb({l3, i, L, R});
                    all.pb({r3 + 1, i, -1, -1});
                }
            }
        }
    }
    
    auto cmp = [&](arr4 x, arr4 y){
        if (x[0] != y[0]) return x[0] < y[0];
        return x[2] < y[2];
    };
    
    sort(all.begin(), all.end(), cmp);
    
    vector<ll> L(n + 1, -1), R(n + 1, -1);
    
    ll out = 0;
    int i1 = 0;
    ST T(a);
    
    auto add = [&](ll l, ll r, int x){
        if ((r - l + 1) >= a){
            T.add(1, a, x);
            return;
        }
        l %= a; r %= a;
        if (l <= r){
            T.add(l + 1, r + 1, x);
            return;
        }
        if (l < a) T.add(l + 1, a, x);
        T.add(1, r + 1, x);
    };

    while (i1 < all.size()){
        int j = i1;
        while (j < all.size() && all[i1][0] == all[j][0]){
            int i = (int) all[j][1];
            if (L[i] != -1){
                if (L[i] <= R[i]) add(L[i], R[i], -1);
            }
            
            L[i] = all[j][2]; R[i] = all[j][3];
            if (L[i] != -1 && L[i] <= R[i]) add(L[i], R[i], 1);
            
            j++;
        }
        
        ll R = 0;
        if (j == all.size()){
            R = b - 1;
        }
        else {
            R = all[j][0] - 1;
        }

        out += 1LL * (R - all[i1][0] + 1) * T.get();
        
        i1 = j;
    }
    
    cout<<out<<"\n";
}

• 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: 20 / 20
• Subtask 8: 0 / 30