| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 971391 |
2024-04-28T12:59:52 Z |
LCJLY |
Passport (JOI23_passport) |
C++14 |
|
2000 ms |
32336 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());
inline pii combine(pii a, pii b){
return {min(a.first,b.first),max(a.second,b.second)};
}
struct node{
int s,e,m;
node *l,*r;
pii v;
node(int ss, int ee):s(ss),e(ee),m((s+e)>>1){
v={0,0};
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void upd(int x, pii y){
if(s==e){
v=y;
return;
}
if(x<=m) l->upd(x,y);
else r->upd(x,y);
v=combine(l->v,r->v);
}
pii query(int x, int y){
if(x<=s&&y>=e){
return v;
}
if(y<=m) return l->query(x,y);
if(x>m) return r->query(x,y);
return combine(l->query(x,m),r->query(m+1,y));
}
};
void solve(){
int n;
cin >> n;
pii arr[n+5];
node st(0,n+5);
for(int x=1;x<=n;x++){
cin >> arr[x].first >> arr[x].second;
st.upd(x,arr[x]);
}
int ans[n+5];
for(int x=1;x<=n;x++){
int l=arr[x].first;
int r=arr[x].second;
int counter=1;
while(l!=1||r!=n){
pii hold=st.query(l,r);
if(hold==make_pair(l,r)) break;
l=hold.first;
r=hold.second;
counter++;
}
if(l!=1||r!=n){
ans[x]=-1;
}
else{
ans[x]=counter;
}
}
int q;
cin >> q;
int temp;
for(int x=0;x<q;x++){
cin >> temp;
cout << ans[temp] << "\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();
}
}
| # |
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 |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
181 ms |
32032 KB |
Output is correct |
| 5 |
Execution timed out |
2045 ms |
32336 KB |
Time limit exceeded |
| 6 |
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 |
0 ms |
460 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
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 |
0 ms |
460 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
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 |
0 ms |
460 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
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 |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
181 ms |
32032 KB |
Output is correct |
| 5 |
Execution timed out |
2045 ms |
32336 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
