Submission #1211056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211056		Tob	Passport (JOI23_passport)	C++20	6 / 100	503 ms	88636 KiB

passport

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int N = 2e5 + 7, ofs = (1 << 18);

int n;
int l[N], r[N], t[2*ofs], d[2*ofs];
int f[2][N];
vector <int> td[N];
vector <pii> adj[2*ofs];

void add(int x, int y) {
	x += ofs;
	t[x] = y;
	while (x /= 2) t[x] = min(t[2*x], t[2*x+1]);
}

int get(int x, int l, int r, int lo = 0, int hi = ofs-1) {
	if (r < lo || hi < l) return ofs;
	if (l <= lo && hi <= r) return t[x];
	int mid = (lo+hi)/2;
	return min(get(2*x, l, r, lo, mid), get(2*x+1, l, r, mid+1, hi));
}

void dod(int x, int l, int r, int y, int lo = 0, int hi = ofs-1) {
	if (r < lo || hi < l) return;
	if (l <= lo && hi <= r) {
		adj[x].pb({y, 1});
		return;
	}
	int mid = (lo+hi)/2;
	dod(2*x, l, r, y, lo, mid);
	dod(2*x+1, l, r, y, mid+1, hi);
}

int main () {
	FIO;
	cin >> n;
	
	for (int i = 1; i < ofs; i++) {
		adj[2*i].pb({i, 0});
		adj[2*i+1].pb({i, 0});
	}
	
	for (int i = 0; i < n; i++) {
		cin >> l[i] >> r[i]; l[i]--; r[i]--;
	}
	
	for (int o = 0; o < 2; o++) {
		fill(t, t+2*ofs, ofs);
		add(n-1, 0);
		for (int i = n-2; i >= 0; i--) {
			if (r[i] == i) f[o][i] = ofs;
			else if (r[i] < n-1) f[o][i] = get(1, i, r[i])+1;
			add(i, f[o][i]);
		}
		reverse(l, l+n);
		reverse(r, r+n);
		for (int i = 0; i < n; i++) {
			l[i] = n-l[i]-1;
			r[i] = n-r[i]-1;
			swap(l[i], r[i]);
		}
	}
	
	for (int i = 0; i < n; i++) {
		int x = f[0][i]+f[1][n-i-1]+1;
		if (x < ofs) td[x].pb(i+ofs);
		dod(1, l[i], r[i], i+ofs);
	}
	
	memset(d, -1, sizeof d);
	for (int i = 0; i < N; i++) {
		while (!td[i].empty()) {
			int x = td[i].back();
			td[i].pop_back();
			if (d[x] != -1) continue;
			d[x] = i;
			for (auto y : adj[x]) if (d[y.F] == -1) {
				td[d[x]+y.S].pb(y.F);
			}
		}
	}
	
	int q; cin >> q;
	for (int i = 0; i < q; i++) {
		int x; cin >> x;
		cout << d[x-1+ofs] << "\n";
	}

	return 0;
}

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