Submission #978814

#	Time	Username	Problem	Language	Result	Execution time	Memory
978814		MilosMilutinovic	Escape Route 2 (JOI24_escape2)	C++14	100 / 100	1211 ms	242016 KiB

Main

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int blk=210;
int n,t,q;
int m[100005];
vector<pii> a[100005];
vector<int> nxt[100005];
vector<int> idx[100005][18];
vector<ll> jmp[100005][18];
ll ans[300005],bst[100005];
vector<pii> qs[100005];
vector<ll> dist[100005];
int lg2[100005];
vector<bool> ok[100005];

ll lift(int x,int y,int d){
	ll ret=0;
	while(d){
		ret+=jmp[x][lg2[d]][y];
		y=idx[x][lg2[d]][y];
		x+=(1<<lg2[d]);
		d-=(1<<lg2[d]);
	}
	return ret;
}

int main(){
	n=readint(); t=readint();
	for(int i=1;i<n;i++){
		m[i]=readint();
		a[i].resize(m[i]);
		for(int j=0;j<m[i];j++){
			a[i][j].fi=readint();
			a[i][j].se=readint();
		}
		sort(a[i].begin(),a[i].end());
	}
	for(int i=1;i<n;i++){
		nxt[i]=vector<int>(m[i],-1);
		for(int j=0;j<18;j++){
			jmp[i][j]=vector<ll>(m[i],0);
			idx[i][j]=vector<int>(m[i],0);
		}
		ok[i]=vector<bool>(m[i],true);
		if(i+1==n) break;
		vector<int> ord(m[i]);
		iota(ord.begin(),ord.end(),0);
		sort(ord.begin(),ord.end(),[&](int x,int y){
			if(a[i][x].se!=a[i][y].se) return a[i][x].se<a[i][y].se;
			else return a[i][x].fi<a[i][y].fi;
		});
		int sz=m[i+1];
		vector<int> mn(sz);
		mn[sz-1]=sz-1;
		for(int j=sz-2;j>=0;j--){
			mn[j]=(a[i+1][j].se<=a[i+1][mn[j+1]].se?j:mn[j+1]);
		}
		int ptr=0;
		for(int j=0;j<m[i];j++){
			while(ptr<m[i+1]&&a[i+1][ptr].fi<a[i][ord[j]].se) ptr++;
			nxt[i][ord[j]]=(ptr==m[i+1]?mn[0]:mn[ptr]);
			jmp[i][0][ord[j]]=(a[i][ord[j]].se<=a[i+1][nxt[i][ord[j]]].fi?a[i+1][nxt[i][ord[j]]].fi-a[i][ord[j]].se:t-a[i][ord[j]].se+a[i+1][nxt[i][ord[j]]].fi)+(a[i+1][nxt[i][ord[j]]].se-a[i+1][nxt[i][ord[j]]].fi);
			idx[i][0][ord[j]]=nxt[i][ord[j]];
		}
		for(int j=0;j<m[i];j++) ord[j]=j;
		sort(ord.begin(),ord.end(),[&](int x,int y){
			if(nxt[i][x]!=nxt[i][y]) return nxt[i][x]<nxt[i][y];
			else return jmp[i][0][x]+a[i][x].se-a[i][x].fi<jmp[i][0][y]+a[i][y].se-a[i][y].fi;
		});
		for(int j=0;j<m[i];j++){
			int ptr=j;
			while(ptr+1<m[i]&&nxt[i][ord[j]]==nxt[i][ord[ptr+1]]) ptr++;
			for(int r=j+1;r<=ptr;r++) ok[i][ord[r]]=false;
			j=ptr;
		}
	}
	for(int i=2;i<=n;i++) lg2[i]=lg2[i>>1]+1;
	for(int k=1;k<18;k++){
		for(int i=1;i+1+(1<<k)<=n;i++){
			for(int j=0;j<m[i];j++){
				jmp[i][k][j]=jmp[i][k-1][j]+jmp[i+(1<<(k-1))][k-1][idx[i][k-1][j]];
				idx[i][k][j]=idx[i+(1<<(k-1))][k-1][idx[i][k-1][j]];
			}
		}
	}
	q=readint();
	for(int i=1;i<=q;i++){
		int l=readint(),r=readint();
		--r;
		qs[l].pb(mp(r,i));
	}
	for(int i=1;i<n;i++){
		dist[i].resize(m[i]);
	}
	for(int i=1;i<=n;i++){
		if(m[i]<=blk){
			for(auto p:qs[i]){
				ans[p.se]=(ll)1e18;
				if(p.fi==i){
					for(int j=0;j<m[i];j++) chkmin(ans[p.se],(ll)a[i][j].se-a[i][j].fi);
				}
			}
			for(int j=0;j<m[i];j++){
				if(!ok[i][j]) continue;
				for(auto p:qs[i]) ans[p.se]=min(ans[p.se],a[i][j].se-a[i][j].fi+lift(i,j,p.fi-i));
			}
			continue;
		}
		int mx=0;
		for(auto p:qs[i]) chkmax(mx,p.fi);
		for(int j=i;j<=mx;j++){
			for(int k=0;k<m[j];k++){
				dist[j][k]=(ll)1e18;
			}
			bst[j]=(ll)1e18;
		}
		priority_queue<pair<ll,pii>> pq;
		for(int j=0;j<m[i];j++){
			dist[i][j]=a[i][j].se-a[i][j].fi;
			pq.push(mp(-dist[i][j],mp(i,j)));
		}
		while(!pq.empty()){
			pair<ll,pii> p=pq.top();
			pq.pop();
			if(dist[p.se.fi][p.se.se]!=-p.fi) continue;
			int x=p.se.fi,y=p.se.se;
			chkmin(bst[x],dist[x][y]);
			if(x>=mx) continue;
			if(dist[x+1][nxt[x][y]]>dist[x][y]+jmp[x][0][y]){
				dist[x+1][nxt[x][y]]=dist[x][y]+jmp[x][0][y];
				pq.push(mp(-dist[x+1][nxt[x][y]],mp(x+1,nxt[x][y])));
			}
		}
		for(auto p:qs[i]) ans[p.se]=bst[p.fi];
	}
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 17 / 17
• Subtask 4: 23 / 23
• Subtask 5: 36 / 36
• Subtask 6: 10 / 10