oj.uz

Submission #730488

# Submission time Handle Problem Language Result Execution time Memory
730488 2023-04-26T03:20:46 Z kym Passport (JOI23_passport) C++14
16 / 100
 2000 ms 100064 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
#define DEC(i,s,e) for(int i = s; i >= (int)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define reach 
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <int, int> pi;
typedef tuple<int,int,int> ti3;
typedef tuple<int,int,int,int> ti4;
int rand(int a, int b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> void chmax(T& a, const T b) { a=max(a,b); }
template <typename T> void chmin(T& a, const T b) { a=min(a,b); }
const int MAXN = 2505;
int n;
int L[MAXN],R[MAXN];
int memo[MAXN][MAXN];
int dpdp(int l, int r){
	if(~memo[l][r])return memo[l][r];
	if(l==1&&r==n)return 0;
	int &ans=memo[l][r];
	ans=oo;
	FOR(i,l,r){
		int nL=min(l,L[i]);
		int nR=max(r,R[i]);
		chmin(ans,1+dpdp(nL,nR));
	}
	return ans;
}
int32_t main() 
{
	IAMSPEED
	
	cin >> n;
	FOR(i,1,n)cin>>L[i]>>R[i];
	int q; cin >> q;
	while(q--){
		memset(memo,-1,sizeof memo);
		int x; cin>>x;
		int res=dpdp(x,x);
		if(res==oo)cout<<-1<<'\n';
		else cout<<res<<'\n';
	}
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 49352 KB Output is correct
2 Correct 25 ms 49440 KB Output is correct
3 Correct 21 ms 49364 KB Output is correct
4 Runtime error 70 ms 100064 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 18 ms 49364 KB Output is correct
2 Correct 22 ms 49396 KB Output is correct
3 Correct 19 ms 49324 KB Output is correct
4 Correct 26 ms 49392 KB Output is correct
5 Correct 21 ms 49364 KB Output is correct
6 Correct 24 ms 49388 KB Output is correct
7 Correct 25 ms 49380 KB Output is correct
8 Correct 21 ms 49340 KB Output is correct
9 Correct 20 ms 49364 KB Output is correct
10 Correct 20 ms 49364 KB Output is correct
11 Correct 22 ms 49336 KB Output is correct
12 Correct 24 ms 49436 KB Output is correct
13 Correct 20 ms 49364 KB Output is correct
14 Correct 21 ms 49352 KB Output is correct
15 Correct 28 ms 49416 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 49364 KB Output is correct
2 Correct 22 ms 49396 KB Output is correct
3 Correct 19 ms 49324 KB Output is correct
4 Correct 26 ms 49392 KB Output is correct
5 Correct 21 ms 49364 KB Output is correct
6 Correct 24 ms 49388 KB Output is correct
7 Correct 25 ms 49380 KB Output is correct
8 Correct 21 ms 49340 KB Output is correct
9 Correct 20 ms 49364 KB Output is correct
10 Correct 20 ms 49364 KB Output is correct
11 Correct 22 ms 49336 KB Output is correct
12 Correct 24 ms 49436 KB Output is correct
13 Correct 20 ms 49364 KB Output is correct
14 Correct 21 ms 49352 KB Output is correct
15 Correct 28 ms 49416 KB Output is correct
16 Execution timed out 2065 ms 49384 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 49364 KB Output is correct
2 Correct 22 ms 49396 KB Output is correct
3 Correct 19 ms 49324 KB Output is correct
4 Correct 26 ms 49392 KB Output is correct
5 Correct 21 ms 49364 KB Output is correct
6 Correct 24 ms 49388 KB Output is correct
7 Correct 25 ms 49380 KB Output is correct
8 Correct 21 ms 49340 KB Output is correct
9 Correct 20 ms 49364 KB Output is correct
10 Correct 20 ms 49364 KB Output is correct
11 Correct 22 ms 49336 KB Output is correct
12 Correct 24 ms 49436 KB Output is correct
13 Correct 20 ms 49364 KB Output is correct
14 Correct 21 ms 49352 KB Output is correct
15 Correct 28 ms 49416 KB Output is correct
16 Execution timed out 2065 ms 49384 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 49352 KB Output is correct
2 Correct 25 ms 49440 KB Output is correct
3 Correct 21 ms 49364 KB Output is correct
4 Runtime error 70 ms 100064 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -