题解：P14332 [JOI2021 预选赛 R2] 活动巡游 / Event Hopping

· · 题解

活动以时刻升序排序，同时同一时刻按城镇排序。设 dp 表示以某活动结束时能参加的最大活动数。处理当前活动 (city, time) 时有两种来源：同城延续使用 bestsame_{city}，得到转移 bestsame_{city}+1；跨城转移需要满足 lst + travel ≤ time - 0.1，化简得 key = lst + K \times dp，只需检查 key ≤ time - D - 1。整体时间复杂度为 O(n\log n)。

参考代码 

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

#define ll long long
const int N=1e6+5;

struct E{
    int c;
    ll t;
};

#define fi first
#define se second

struct M{
    map<ll,int> mp;
    void add(ll k,int v){
        auto it=mp.lower_bound(k);
        if(it!=mp.end()&&it->fi==k){
            if(it->se>=v) return;
            it=mp.erase(it);
        }
        if(it!=mp.begin()){
            auto pr=prev(it);
            if(pr->se>=v) return;
        }
        while(it!=mp.end()&&it->se<=v) it=mp.erase(it);
        mp.emplace_hint(it,k,v);
    }
    int get(ll lim){
        auto it=mp.upper_bound(lim);
        if(it==mp.begin()) return 0;
        it--;
        return it->se;
    }
};

bool cmp(E&a,E&b){
    if(a.t!=b.t) return a.t<b.t;
    return a.c<b.c;
}

void solve(){
    int n;
    ll d,K0;
    cin>>n>>d>>K0;
    vector<E> e(n);
    for(int i=0;i<n;i++){
        int p; ll s;
        cin>>p>>s;
        e[i]={p-1,s};
    }
    sort(e.begin(),e.end(),cmp);
    M ord[2];
    int bs[2]={0,0},ans=0;
    for(auto&e:e){
        int c=e.c;
        ll t=e.t;
        int f=max(1,bs[c]+1);
        ll lim=t-d-1;
        int cross=ord[c^1].get(lim);
        f=max(f,cross+1),bs[c]=max(bs[c],f);
        ll k2=t+K0*f;
        ord[c].add(k2,f),ans=max(ans,f);
    }
    cout<<ans<<'\n';
    return;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    solve();

    return 0;
}