Submission #838190

#	Time	Username	Problem	Language	Result	Execution time	Memory
838190		fatemetmhr	Passport (JOI23_passport)	C++17	48 / 100	2073 ms	4024 KiB

passport

// na hanooz omidi vjood dare... hanooz ye karayi hast ke bknm :)

#include <bits/stdc++.h>

using namespace std;


#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)   (x).begin(), (x).end()
#define fi       first
#define se       second
#define mp       make_pair
#define pb       push_back

typedef long long ll;

const int maxn5 = 2e5 + 10;
const int lg    = 20;

int suf[maxn5], pre[maxn5], ans[maxn5];
int l[maxn5], r[maxn5];
bool mark[maxn5];
pair <int, int> per[maxn5];


int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	int n; cin >> n;
	for(int i = 0; i < n; i++){
		cin >> l[i] >> r[i];
		per[i] = {r[i] - l[i], i};
		l[i]--; r[i]--;
	}
	sort(per, per + n);
	reverse(per, per + n);
	fill(ans, ans + n + 5, maxn5);
	for(int i = 0; i < n; i++){
		int v = per[i].se;
		int cnt = 0;
		int lq = l[v], pt = r[v];
		bool con = true;
		while(con && lq > 0){
			con = false;
			cnt++;
			int keepl = lq;
			while(pt >= keepl){
				con = true;
				lq = min(lq, l[pt]);
				ans[v] = min(ans[v], ans[pt] + cnt);
				pt--;
			}
		}
		if(lq > 0)
			cnt = maxn5;
		int keep = cnt;
		cnt = 0;
		int rq = r[v]; pt = l[v];
		con = true;
		while(rq < n - 1 && con){
			con = false;
			cnt++;
			int keepr = rq;
			while(pt <= keepr){
				con = true;
				rq = max(rq, r[pt]);
				ans[v] = min(ans[v], ans[pt] + cnt);
				pt++;
			}
		}
		if(rq < n - 1)
			cnt = maxn5;
		ans[v] = min(ans[v], cnt + keep);
	}

	int q; cin >> q;
	for(int i = 0; i < q; i++){
		int x; cin >> x;
		x--;
		cout << (ans[x] >= maxn5 ? -1 : ans[x] + 1) << '\n';
	}

}

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