Submission #626984

#	Time	Username	Problem	Language	Result	Execution time	Memory
626984		socpite	Strange Device (APIO19_strange_device)	C++14	100 / 100	3924 ms	259124 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;

const int maxn = 2e6+5;

int n, sz;
ll a, b;

pair<ll, ll> A[maxn];
vector<pair<int, int>> qq[maxn];
map<ll, int> mp;
vector<pair<ll, ll>> rng, vec;
vector<ll> pos;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b;
    ll cyc = a/__gcd(a, b+1);
    for(int i = 0; i < n; i++){
        cin >> A[i].f >> A[i].s;
        ll lb = A[i].f/b+1, rb = A[i].s/b-1;
        if(rb >= lb){
            if(rb - lb+1 >= cyc)rng.push_back({0, cyc-1});
            else{
                ll lm = lb%cyc, rm = rb%cyc;
                if(lm <= rm)vec.push_back({lm, rm});
                else{
                    vec.push_back({lm, cyc-1});
                    vec.push_back({0, rm});
                }
            }
        }
        pos.push_back(A[i].f%b);
        pos.push_back(A[i].s%b + 1);
    }
    pos.push_back(-1);
    pos.push_back(0);
    pos.push_back(b);
    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());
    sort(vec.begin(), vec.end());
    for(auto v: vec){
        if(rng.empty() || rng.back().s < v.f-1)rng.push_back(v);
        else rng.back().s = max(rng.back().s, v.s);
    }
    sz = pos.size()-1;
    for(int i = 0; i < n; i++){
        ll lb = A[i].f/b, rb = A[i].s/b;
        if(lb == rb){
            int pp = lower_bound(rng.begin(), rng.end(), make_pair(lb%cyc, cyc+1))-rng.begin()-1;
            if(pp < 0 || rng[pp].s < lb%cyc){
                int ql = lower_bound(pos.begin(), pos.end(), A[i].f%b)-pos.begin(), qr = upper_bound(pos.begin(), pos.end(), A[i].s%b) - pos.begin();
                qq[ql].push_back({lb%cyc, 0});
                qq[qr].push_back({lb%cyc, 1});
            }
        }
        else{
            int pp = lower_bound(rng.begin(), rng.end(), make_pair(lb%cyc, cyc+1))-rng.begin()-1;
            if(pp < 0 || rng[pp].s < lb%cyc){
                int ql = lower_bound(pos.begin(), pos.end(), A[i].f%b)-pos.begin();
                qq[ql].push_back({lb%cyc, 0});
            }
            pp = lower_bound(rng.begin(), rng.end(), make_pair(rb%cyc, cyc+1))-rng.begin()-1;
            if(pp < 0 || rng[pp].s < rb%cyc){
                int qr = upper_bound(pos.begin(), pos.end(), A[i].s%b) - pos.begin();
                qq[1].push_back({rb%cyc, 0});
                qq[qr].push_back({rb%cyc, 1});
            }
        }
    }
    int crr = 0;
    ll ans = 0;
    for(int i = 1; i < sz; i++){
        for(auto v: qq[i]){
            if(v.s){
                mp[v.f]--;
                if(!mp[v.f])crr--;
            }
            else{
                if(!mp[v.f])crr++;
                mp[v.f]++;
            }
        }
        ans += (pos[i+1]-pos[i])*crr;
    }
    for(auto v: rng){
        ans+=b*(v.s-v.f+1);
    }
    cout << ans;
}

• 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