#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
tomorrow will worse
but the day after tomorrow will be the sunshine..
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
bool cp(pii a, pii b){return a.ss < b.ss;}
int inter(pii a, pii b){
if(a.ff > b.ss || a.ss < b.ff)return 0;
return (a.ss-a.ff)-max(0ll, min(a.ss, b.ss) - max(a.ff, b.ff));
}
void solve(){
int n;
cin >> n;
vii a(n);
set<pii> b;
for(int i = 0; i < n; i++){
cin >> a[i].ff >> a[i].ss;
b.insert(a[i]);
}
int q;
cin >> q;
while(q--){
int l, r, i;
cin >> i;i--;
l = a[i].ff, r = a[i].ss;
int cnt = 1;
while(l > 1 || r < n){
int x = -1, mx = 0;
for(int i = l-1; i < r; i++){
if(inter(a[i],{l, r}) > mx){
mx = inter(a[i],{l, r});
x = i;
}
}
if(mx == 0)break;
l = min(l, a[x].ff);
r = max(r, a[x].ss);
cnt++;
//~ cout << mx << ' ' << x << ' ' << l << ' ' << r << '\n';
}
if(l == 1 && r == n)cout << cnt << '\n';
else cout << "-1\n";
}
}
main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t = 1;
//~ cin >> t;
while(t--){
solve();
}
}
Compilation message
passport.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
58 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
81 ms |
15604 KB |
Output is correct |
| 5 |
Execution timed out |
2032 ms |
15648 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
81 ms |
15604 KB |
Output is correct |
| 5 |
Execution timed out |
2032 ms |
15648 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
