打 duels 打到的题，调不出来 /ll

CF311C WA #3 求调，悬赏 4 关

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
inline int read(){
    int res=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
    return res*f;
}
const int N=1e5+5,K=1e4+5;
int h,n,m,k,vis[N],d[N],f[N];
struct Node{
    int x,y,i;
    bool operator<(Node _)const{
        return y<_.y;
    }
}a[N];
set<Node>s;
vector<pair<int,int> >e[K];
void dijkstra(int x){
    for (int i=0;i<=k;i++)
        e[i].clear();
    for (int i=0;i<k;i++){
        e[i].push_back({(i+x)%k,(i+x)/k});
        e[k].push_back({i,d[i]});
    }
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >que;
	bitset<K>tmp;
	for (int i=0;i<k;i++)
        f[i]=2e18;
	d[k]=0;
	que.push({0,k});
	while (!que.empty()){
		int u=que.top().sc,fu=que.top().fr;
		que.pop();
		if (tmp[u]||fu!=f[u]) continue;
		tmp[u]=1;
		for (auto i:e[u]){
			int v=i.fr,w=i.sc;
			if (f[v]>fu+w){
				f[v]=fu+w;
				que.push({f[v],v});
			}
		}
	}
    for (int i=0;i<k;i++)
        d[i]=min(d[i],f[i]);
}
bool check(int x){
    return d[x%k]<=x/k;
}
void ins(int x){
    dijkstra(x);
    for (int i=1;i<=n;i++)
        if (!vis[i]&&check(a[i].x))
            s.insert(a[i]),vis[i]=1;
}
signed main(){
    h=read(),n=read(),m=read(),k=read();
    for (int i=1;i<k;i++)
        d[i]=2e18;d[0]=1;
    for (int i=1;i<=n;i++)
        a[i]={read()-1,read(),i};
    for (int i=1;i<=n;i++)
        if (!vis[i]&&check(a[i].x))
            s.insert(a[i]),vis[i]=1;
    while (m--){
        int op=read();
        if (op==1){
            int x=read();
            ins(x);
        }
        if (op==2){
            int x=read(),d=read();
            if (!vis[x]) a[x].y-=d;
            else{
                s.erase(a[x]);
                a[x].y-=d;
                s.insert(a[x]);
            }
        }
        if (op==3){
            if (s.size()==0) cout<<0<<'\n';
            else{
                cout<<(*s.rbegin()).y<<'\n';
                vis[(*s.rbegin()).i]=1;
                s.erase(*s.rbegin());
            }
        }
    }
    return 0;
}