Submission #888892

#	Time	Username	Problem	Language	Result	Execution time	Memory
888892		Nurislam	Passport (JOI23_passport)	C++14	22 / 100	53 ms	59632 KiB

passport

#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;
const int N = 2e5+50, inf = 1e18;

int n;
pii stmn[20][N];
pii stmx[20][N];
pii getmn(int l, int r) {
    int cl = __lg(r - l + 1);
    if(min(stmn[cl][l].ff, stmn[cl][r - (1 << cl) + 1].ff) == stmn[cl][l].ff)return stmn[cl][l];
    return stmn[cl][r - (1 << cl) + 1];
}
pii getmx(int l, int r) {
    int cl = __lg(r - l + 1);
    if(max(stmx[cl][l].ff, stmx[cl][r - (1 << cl) + 1].ff) == stmx[cl][l].ff)return stmx[cl][l];
    return stmx[cl][r - (1 << cl) + 1];
}

void solve(){
	int n;
	cin >> n;
	vii a(n+1);
	for(int i = 1; i <= n; i++){
		int l, r;
		cin >> l >> r;
		a[i] = {l, r};
		stmn[0][i] = {l, i};
		stmx[0][i] = {r, i};
	}
    for (int i = 1; i <= __lg(n); i++) {
        int len = 1 << (i - 1);
        for (int j = 1; j <= n; j++) {
            stmn[i][j] = stmn[i - 1][j];
            if(stmn[i][j].ff > stmn[i-1][min(j+len, n)].ff) stmn[i][j] = stmn[i - 1][ min(j + len, n) ];
            if(stmn[i][j].ff == stmn[i-1][min(j+len, n)].ff){
				if(a[stmn[i][j].ss].ss < a[stmn[i-1][min(j+len, n)].ss].ss)stmn[i][j] = stmn[i-1][min(j+len, n)];
			}
        }
    }
    for (int i = 1; i <= __lg(n); i++) {
        int len = 1 << (i - 1);
        for (int j = 1; j <= n; j++) {
            stmx[i][j] = stmx[i - 1][j];
            if(stmx[i][j].ff < stmx[i-1][min(j+len, n)].ff) stmx[i][j] = stmx[i - 1][ min(j + len, n) ];
            if(stmx[i][j].ff == stmx[i-1][min(j+len, n)].ff){
				if(a[stmx[i][j].ss].ff > a[stmx[i-1][min(j+len, n)].ss].ff)stmx[i][j] = stmx[i-1][min(j+len, n)];
			}
        }
    }
	int q;
	cin >> q;
	while(q--){
		int ans = inf;
		int x;
		cin >> x;
		set<pair<int,pii>> q;
		q.insert({1, a[x]});
		int l, r, _l, _r;
		while(!q.empty()){
			auto [cnt, tu] = *q.begin();
			q.erase(q.begin());
			l = tu.ff,r = tu.ss;
			if(l == 1 && r == n){
				ans = min(ans, cnt);
				continue;
			}
			pii fr = getmn(l, r);
			_l = min(l, fr.ff), _r = max(r, a[fr.ss].ss);
			if(l != _l || r != _r)q.insert({cnt+1, {_l, _r}});
			pii sc = getmx(l, r);
			if(sc.ss == fr.ss)continue;
			_l = min(l, a[sc.ss].ff), _r = max(r, sc.ff);
			if(l != _l || r != _r)q.insert({cnt+1, {_l, _r}});
		}
		cout << (ans == inf?-1:ans) << '\n';
	}
}
main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t = 1;
  //~ cin >> t;
  while(t--){
    solve();
  }
}

Compilation message (stderr)

passport.cpp:19:29: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const int N = 2e5+50, inf = 1e18;
      |                             ^~~~
passport.cpp: In function 'void solve()':
passport.cpp:76:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |    auto [cnt, tu] = *q.begin();
      |         ^
passport.cpp: At global scope:
passport.cpp:94:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   94 | main(){
      | ^~~~

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