제출 #1146260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146260		vladilius	Strange Device (APIO19_strange_device)	C++20	40 / 100	1729 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{
        node *l, *r;
        int m; ll c, p;
        node(ll x){
            l = r = 0;
            m = p = 0; c = x;
        }
    };
    ll n;
    node *rt;
    ST(ll ns){
        n = ns;
        rt = new node(n);
    }
    void push(node *v){
        if (!(v -> p)) return;
        v -> l -> m += v -> p;
        v -> r -> m += v -> p;
        v -> l -> p += v -> p;
        v -> r -> p += v -> p;
        v -> p = 0;
    }
    void add(node *v, ll tl, ll tr, ll l, ll r, int x){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            v -> m += x;
            v -> p += x;
            return;
        }
        ll tm = (tl + tr) / 2;
        if (!(v -> l)) v -> l = new node(tm - tl + 1);
        if (!(v -> r)) v -> r = new node(tr - tm);
        push(v);
        add(v -> l, tl, tm, l, r, x);
        add(v -> r, tm + 1, tr, l, r, x);
        v -> m = min(v -> l -> m, v -> r -> m);
        v -> c = 0;
        if (v -> l -> m == v -> m) v -> c += v -> l -> c;
        if (v -> r -> m == v -> m) v -> c += v -> r -> c;
    };
    void add(ll l, ll r, int x){
        add(rt, 1, n, l, r, x);
    }
    ll get(){
        ll out = n;
        if (!(rt -> m)) out -= rt -> 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