oj.uz

Submission #971482

# Submission time Handle Problem Language Result Execution time Memory
971482 2024-04-28T16:15:53 Z LCJLY Passport (JOI23_passport) C++14
48 / 100
 1745 ms 50004 KB 
#include <bits/stdc++.h>
using namespace std;
	
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,long long>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
 
pii arr[2505];
int n;
int memo[2505][2505];
 
int dp(int l, int r){
	if(l==1&&r==n) return 0;
	if(memo[l][r]!=-1) return memo[l][r];
	int ans=1e15;
	for(int x=l;x<=r;x++){
		if(arr[x].first<l||arr[x].second>r){
			ans=min(ans,dp(min(l,arr[x].first),max(r,arr[x].second))+1);
		}
	}
	return memo[l][r]=ans;
}
 
void solve(){
	cin >> n;
	for(int x=1;x<=n;x++){
		cin >> arr[x].first >> arr[x].second;
	}
	
	int q;
	cin >> q;
	int temp;
	memset(memo,-1,sizeof(memo));
	for(int x=0;x<q;x++){
		cin >> temp;
		int hold=dp(arr[temp].first,arr[temp].second);
		if(hold>1e12){
			cout << -1 << "\n";
		}
		else cout << hold+1 << "\n";
	}
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//freopen("in.txt","r",stdin);
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 49500 KB Output is correct
2 Correct 18 ms 49500 KB Output is correct
3 Correct 17 ms 49500 KB Output is correct
4 Runtime error 2 ms 600 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49500 KB Output is correct
2 Correct 20 ms 49636 KB Output is correct
3 Correct 18 ms 49500 KB Output is correct
4 Correct 19 ms 49500 KB Output is correct
5 Correct 18 ms 49496 KB Output is correct
6 Correct 18 ms 49500 KB Output is correct
7 Correct 19 ms 49500 KB Output is correct
8 Correct 18 ms 49500 KB Output is correct
9 Correct 18 ms 49556 KB Output is correct
10 Correct 18 ms 49500 KB Output is correct
11 Correct 19 ms 49564 KB Output is correct
12 Correct 20 ms 49500 KB Output is correct
13 Correct 20 ms 49496 KB Output is correct
14 Correct 22 ms 49496 KB Output is correct
15 Correct 19 ms 49496 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49500 KB Output is correct
2 Correct 20 ms 49636 KB Output is correct
3 Correct 18 ms 49500 KB Output is correct
4 Correct 19 ms 49500 KB Output is correct
5 Correct 18 ms 49496 KB Output is correct
6 Correct 18 ms 49500 KB Output is correct
7 Correct 19 ms 49500 KB Output is correct
8 Correct 18 ms 49500 KB Output is correct
9 Correct 18 ms 49556 KB Output is correct
10 Correct 18 ms 49500 KB Output is correct
11 Correct 19 ms 49564 KB Output is correct
12 Correct 20 ms 49500 KB Output is correct
13 Correct 20 ms 49496 KB Output is correct
14 Correct 22 ms 49496 KB Output is correct
15 Correct 19 ms 49496 KB Output is correct
16 Correct 1101 ms 49596 KB Output is correct
17 Correct 394 ms 49628 KB Output is correct
18 Correct 25 ms 49500 KB Output is correct
19 Correct 39 ms 49672 KB Output is correct
20 Correct 1084 ms 49772 KB Output is correct
21 Correct 486 ms 50000 KB Output is correct
22 Correct 19 ms 49500 KB Output is correct
23 Correct 1110 ms 49692 KB Output is correct
24 Correct 577 ms 49624 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49500 KB Output is correct
2 Correct 20 ms 49636 KB Output is correct
3 Correct 18 ms 49500 KB Output is correct
4 Correct 19 ms 49500 KB Output is correct
5 Correct 18 ms 49496 KB Output is correct
6 Correct 18 ms 49500 KB Output is correct
7 Correct 19 ms 49500 KB Output is correct
8 Correct 18 ms 49500 KB Output is correct
9 Correct 18 ms 49556 KB Output is correct
10 Correct 18 ms 49500 KB Output is correct
11 Correct 19 ms 49564 KB Output is correct
12 Correct 20 ms 49500 KB Output is correct
13 Correct 20 ms 49496 KB Output is correct
14 Correct 22 ms 49496 KB Output is correct
15 Correct 19 ms 49496 KB Output is correct
16 Correct 1101 ms 49596 KB Output is correct
17 Correct 394 ms 49628 KB Output is correct
18 Correct 25 ms 49500 KB Output is correct
19 Correct 39 ms 49672 KB Output is correct
20 Correct 1084 ms 49772 KB Output is correct
21 Correct 486 ms 50000 KB Output is correct
22 Correct 19 ms 49500 KB Output is correct
23 Correct 1110 ms 49692 KB Output is correct
24 Correct 577 ms 49624 KB Output is correct
25 Correct 17 ms 49496 KB Output is correct
26 Correct 20 ms 49500 KB Output is correct
27 Correct 1544 ms 49640 KB Output is correct
28 Correct 813 ms 49688 KB Output is correct
29 Correct 1745 ms 50004 KB Output is correct
30 Correct 578 ms 49740 KB Output is correct
31 Correct 22 ms 49496 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 49500 KB Output is correct
2 Correct 18 ms 49500 KB Output is correct
3 Correct 17 ms 49500 KB Output is correct
4 Runtime error 2 ms 600 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -