oj.uz

Submission #1048941

# Submission time Handle Problem Language Result Execution time Memory
1048941 2024-08-08T11:25:53 Z amirhoseinfar1385 Dungeons Game (IOI21_dungeons) C++17
100 / 100
 6729 ms 380108 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn=400000+10,lg=18,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){
	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;
		}
	}
}
 
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,1e9);
	return ret.ezaf;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18776 KB Output is correct
2 Correct 1 ms 18776 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 36 ms 65748 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 47 ms 65780 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2806 ms 370680 KB Output is correct
3 Correct 3120 ms 370916 KB Output is correct
4 Correct 3402 ms 370912 KB Output is correct
5 Correct 551 ms 370768 KB Output is correct
6 Correct 2750 ms 370744 KB Output is correct
7 Correct 1308 ms 370912 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 59 ms 66524 KB Output is correct
3 Correct 58 ms 66396 KB Output is correct
4 Correct 56 ms 66392 KB Output is correct
5 Correct 56 ms 66396 KB Output is correct
6 Correct 62 ms 66396 KB Output is correct
7 Correct 67 ms 66392 KB Output is correct
8 Correct 59 ms 66392 KB Output is correct
9 Correct 46 ms 66392 KB Output is correct
10 Correct 59 ms 66396 KB Output is correct
11 Correct 50 ms 66392 KB Output is correct
12 Correct 142 ms 66532 KB Output is correct
13 Correct 134 ms 66396 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 59 ms 66524 KB Output is correct
3 Correct 58 ms 66396 KB Output is correct
4 Correct 56 ms 66392 KB Output is correct
5 Correct 56 ms 66396 KB Output is correct
6 Correct 62 ms 66396 KB Output is correct
7 Correct 67 ms 66392 KB Output is correct
8 Correct 59 ms 66392 KB Output is correct
9 Correct 46 ms 66392 KB Output is correct
10 Correct 59 ms 66396 KB Output is correct
11 Correct 50 ms 66392 KB Output is correct
12 Correct 142 ms 66532 KB Output is correct
13 Correct 134 ms 66396 KB Output is correct
14 Correct 2 ms 18780 KB Output is correct
15 Correct 82 ms 66532 KB Output is correct
16 Correct 58 ms 66396 KB Output is correct
17 Correct 62 ms 66568 KB Output is correct
18 Correct 70 ms 66568 KB Output is correct
19 Correct 59 ms 66396 KB Output is correct
20 Correct 157 ms 66396 KB Output is correct
21 Correct 123 ms 66568 KB Output is correct
22 Correct 114 ms 66392 KB Output is correct
23 Correct 54 ms 66400 KB Output is correct
24 Correct 77 ms 66596 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 59 ms 66524 KB Output is correct
3 Correct 58 ms 66396 KB Output is correct
4 Correct 56 ms 66392 KB Output is correct
5 Correct 56 ms 66396 KB Output is correct
6 Correct 62 ms 66396 KB Output is correct
7 Correct 67 ms 66392 KB Output is correct
8 Correct 59 ms 66392 KB Output is correct
9 Correct 46 ms 66392 KB Output is correct
10 Correct 59 ms 66396 KB Output is correct
11 Correct 50 ms 66392 KB Output is correct
12 Correct 142 ms 66532 KB Output is correct
13 Correct 134 ms 66396 KB Output is correct
14 Correct 2 ms 18780 KB Output is correct
15 Correct 82 ms 66532 KB Output is correct
16 Correct 58 ms 66396 KB Output is correct
17 Correct 62 ms 66568 KB Output is correct
18 Correct 70 ms 66568 KB Output is correct
19 Correct 59 ms 66396 KB Output is correct
20 Correct 157 ms 66396 KB Output is correct
21 Correct 123 ms 66568 KB Output is correct
22 Correct 114 ms 66392 KB Output is correct
23 Correct 54 ms 66400 KB Output is correct
24 Correct 77 ms 66596 KB Output is correct
25 Correct 41 ms 65628 KB Output is correct
26 Correct 51 ms 66396 KB Output is correct
27 Correct 134 ms 66392 KB Output is correct
28 Correct 112 ms 66392 KB Output is correct
29 Correct 55 ms 66396 KB Output is correct
30 Correct 247 ms 66532 KB Output is correct
31 Correct 293 ms 66568 KB Output is correct
32 Correct 340 ms 66564 KB Output is correct
33 Correct 105 ms 66396 KB Output is correct
34 Correct 122 ms 66396 KB Output is correct
35 Correct 208 ms 66568 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2806 ms 370680 KB Output is correct
3 Correct 3120 ms 370916 KB Output is correct
4 Correct 3402 ms 370912 KB Output is correct
5 Correct 551 ms 370768 KB Output is correct
6 Correct 2750 ms 370744 KB Output is correct
7 Correct 1308 ms 370912 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 59 ms 66524 KB Output is correct
10 Correct 58 ms 66396 KB Output is correct
11 Correct 56 ms 66392 KB Output is correct
12 Correct 56 ms 66396 KB Output is correct
13 Correct 62 ms 66396 KB Output is correct
14 Correct 67 ms 66392 KB Output is correct
15 Correct 59 ms 66392 KB Output is correct
16 Correct 46 ms 66392 KB Output is correct
17 Correct 59 ms 66396 KB Output is correct
18 Correct 50 ms 66392 KB Output is correct
19 Correct 142 ms 66532 KB Output is correct
20 Correct 134 ms 66396 KB Output is correct
21 Correct 2 ms 18780 KB Output is correct
22 Correct 82 ms 66532 KB Output is correct
23 Correct 58 ms 66396 KB Output is correct
24 Correct 62 ms 66568 KB Output is correct
25 Correct 70 ms 66568 KB Output is correct
26 Correct 59 ms 66396 KB Output is correct
27 Correct 157 ms 66396 KB Output is correct
28 Correct 123 ms 66568 KB Output is correct
29 Correct 114 ms 66392 KB Output is correct
30 Correct 54 ms 66400 KB Output is correct
31 Correct 77 ms 66596 KB Output is correct
32 Correct 41 ms 65628 KB Output is correct
33 Correct 51 ms 66396 KB Output is correct
34 Correct 134 ms 66392 KB Output is correct
35 Correct 112 ms 66392 KB Output is correct
36 Correct 55 ms 66396 KB Output is correct
37 Correct 247 ms 66532 KB Output is correct
38 Correct 293 ms 66568 KB Output is correct
39 Correct 340 ms 66564 KB Output is correct
40 Correct 105 ms 66396 KB Output is correct
41 Correct 122 ms 66396 KB Output is correct
42 Correct 208 ms 66568 KB Output is correct
43 Correct 2 ms 18776 KB Output is correct
44 Correct 2 ms 18780 KB Output is correct
45 Correct 565 ms 370748 KB Output is correct
46 Correct 1647 ms 370912 KB Output is correct
47 Correct 1082 ms 370768 KB Output is correct
48 Correct 2306 ms 370912 KB Output is correct
49 Correct 614 ms 370748 KB Output is correct
50 Correct 2858 ms 370916 KB Output is correct
51 Correct 637 ms 371028 KB Output is correct
52 Correct 2790 ms 370904 KB Output is correct
53 Correct 6729 ms 370768 KB Output is correct
54 Correct 1280 ms 380108 KB Output is correct
55 Correct 2055 ms 379064 KB Output is correct
56 Correct 3314 ms 379688 KB Output is correct
57 Correct 3033 ms 379728 KB Output is correct
58 Correct 2909 ms 379732 KB Output is correct
59 Correct 2555 ms 379984 KB Output is correct
60 Correct 5352 ms 379212 KB Output is correct
61 Correct 4880 ms 378964 KB Output is correct