#include "bits/stdc++.h"
using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define pi pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define mp make_pair
#define ll long long
#define pb push_back
#define vpi vector<pi>
#define all(x) x.begin()+1,x.end()
const int INF = (int)1e17;
// figure out most of the implementation details before you
// implement the whole thing
// try to change the order in which you imlpement certain
// processes (doesnt have to be in chronological order) to
// simplify the implementation
// try to think in different directions and if one direction
// is giving too many edge cases its probably not the intended way
// try to have a fairly clear idea of each segment of code you
// are going to write and divide your idea into organized
// subideas instead of just trying to go off a vague idea without
// figuring out any implementation details
// dont spend too much time on a problem get the subtasks and gtfo
// if you already spent too much time on it
// try to implement subtasks if full implementation is big
// or youre out of ideas to optimize
int n;
vvi dp;
vi L, R;
void dfs(int l, int r, int c)
{
//cout << ' ' << l << ' ' << r << ' ' << c << '\n';
if (dp[l][r] < c) return;
dp[l][r] = c;
rep(i, l, r)
{
pi curr = mp(l, r);
pi next = mp(min(l, L[i]), max(r, R[i]));
if (curr != next) dfs(next.first, next.second, c+1);
}
}
void solve()
{
cin >> n;
L = vi(n+1); R = vi(n+1);
rep(i, 1, n) cin >> L[i] >> R[i];
dp = vvi(n+1, vi(n+1, INF));
int w; cin >> w;
int s; cin >> s;
dp[s][s] = 0;
dfs(s, s, 0);
cout << (dp[1][n] == INF ? -1 : dp[1][n]);
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
auto begin = std::chrono::high_resolution_clock::now();
int t = 1;
//cin >> t;
rep(i, 1, t)
{
//cout << "Case " << i << ":\n";
solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Runtime error |
423 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
295 ms |
980 KB |
Output is correct |
| 12 |
Execution timed out |
2081 ms |
980 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
295 ms |
980 KB |
Output is correct |
| 12 |
Execution timed out |
2081 ms |
980 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
295 ms |
980 KB |
Output is correct |
| 12 |
Execution timed out |
2081 ms |
980 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Runtime error |
423 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
