제출 #1187781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187781		TsotneSV	Passport (JOI23_passport)	C++20	0 / 100	2097 ms	1864 KiB

passport

#include <bits/stdc++.h>
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋       
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

//const int mod = 1e9+7;
//const int mod = 998244353;
const int MAXN=2e5+5; 
const ll inf=1e9,INF=1e18; 

int n,L[MAXN],R[MAXN];

int go(int st,int end) {

    if(st == end) return 1;

    int p = 2;
    
    if(st < end) {

        int curr = st;

        while(R[curr] < end) {
            int c = curr;
            for(int i=(curr == st ? L[curr] : curr);i<=R[curr];i++) {
                if(R[i] > R[c]) c = i;
            }

            if(curr == c) return inf;
            curr = c; p++;
        } return p;

    } else {

        int curr = st;

        while(L[curr] > end) {
            int c = curr;
            for(int i=(curr == st ? R[curr] : curr);i>=L[curr];i--) {
                if(L[i] < L[c]) c = i;
            }

            if(curr == c) return inf;
            curr = c; p++;
        } return p;

    }

}

void solve(int tc = 0){
    cin>>n; 
    
    for(int i=1;i<=n;i++) cin>>L[i]>>R[i];

    int q; cin>>q;

    while(q--) {
        int x,ans = inf; cin>>x; // q ~ n => O(n^3)

        for(int i=1;i<=n;i++) {
            if(L[i] == 1) {
                ans = min(ans,go(x,i) + go(i,n) - 1 - (i != n));
            }
        } 

        for(int i=1;i<=n;i++) {
            if(R[i] == n) {
                ans = min(ans,go(x,i) + go(i,1) - 1 - (i != 1));
            }
        } 
        
        print(ans > 1e6 ? -1 : ans);
    }

}

signed main(){

    ios_base::sync_with_stdio(false); cin.tie(0);

    int tc=1;
    //cin>>tc;
    for(int t = 0; t < tc; t++) solve(t);
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46