Submission #1048956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048956		amirhoseinfar1385	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	6926 ms	415704 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn=400000+10,lg=20,maxm=maxn*2;
long long sp[maxm][lg],wsp[maxm][lg],ezafsp[maxm][lg];
long long n,all[maxm],r[maxm],l[maxm],s[maxm],p[maxm],inf=1e15+5;
struct stbor{
	long long tamam,ezaf,kam;
	stbor(){
		ezaf=0;
		kam=inf;
	}
}fakebor;
 
stbor boro(long long ind,long long now,long long len){
//	cout<<ind<<" "<<now<<" "<<len<<" wtf "<<endl;
	if(ind==n){
		stbor ret;
		ret.ezaf=now;
		ret.kam=inf;
		ret.tamam=ind;
		return ret;
	}
	if(len==0){
		stbor ret;
		ret.ezaf=now;
		ret.kam=inf;
		ret.tamam=ind;
		return ret;
	}
	long long ziad=now;
	long long u=ind;
	if(now>=s[ind]){
		ziad-=s[ind];
	}else{
		u=ind+maxn;
	}
	stbor ret;
	for(long long j=lg-1;j>=0;j--){
		if((1<<j)<=len&&wsp[u][j]>ziad){
			ret=boro(sp[u][j],ezafsp[u][j]+ziad,len-(1<<j));
			ret.kam=min(ret.kam,wsp[u][j]-ziad);
			return ret;
		}
	}
	return ret;
}
 
void calsp(){
	for(long long i=0;i<n;i++){
		sp[i][0]=r[i];
		wsp[i][0]=inf;
		ezafsp[i][0]=s[i]+s[i];
		sp[i+maxn][0]=l[i];
		wsp[i+maxn][0]=inf;
		wsp[i+maxn][0]=s[i];
		ezafsp[i+maxn][0]=p[i];
	}
	sp[n][0]=n;
	wsp[n][0]=inf;
	ezafsp[n][0]=0;
	for(long long lev=1;lev<lg;lev++){
		for(long long i=0;i<=n;i++){
//			cout<<i<<" "<<lev<<endl;
			stbor tof=boro(sp[i][lev-1],ezafsp[i][lev-1],(1<<(lev-1)));
			sp[i][lev]=tof.tamam;
			wsp[i][lev]=min(wsp[i][lev-1],tof.kam);
			ezafsp[i][lev]=tof.ezaf;
			tof=boro(sp[i+maxn][lev-1],ezafsp[i+maxn][lev-1],(1<<(lev-1)));
			sp[i+maxn][lev]=tof.tamam;
			wsp[i+maxn][lev]=min(wsp[i+maxn][lev-1],tof.kam);
			ezafsp[i+maxn][lev]=tof.ezaf;
		}
	}
 
 
//	for(long long i=0;i<=n;i++){
//		for(long long j=0;j<3;j++){
//			cout<<i<<" "<<j<<" "<<sp[i][j]<<" "<<wsp[i][j]<<" "<<ezafsp[i][j]<<endl;
//		}
//	}
}
 
void init(int n_, std::vector<int> s_, std::vector<int> p_, std::vector<int> w_, std::vector<int> l_) {
	n=n_;
	fakebor.tamam=n;
	for(long long i=0;i<n;i++){
		s[i]=s_[i];
		l[i]=l_[i];
		r[i]=w_[i];
		p[i]=p_[i];
	}
	calsp();
	return;
}
 
long long simulate(int x,int z) {
	stbor ret=boro(x,z,2e7);
//	cout<<ret.tamam<<" "<<ret.ezaf<<" "<<ret.kam<<endl;
	return ret.ezaf;
}

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11