Submission #979108

#	Time	Username	Problem	Language	Result	Execution time	Memory
979108		temporary1	Passport (JOI23_passport)	C++17	6 / 100	82 ms	18812 KiB

passport

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second

vector<int> graph[200001];
int to[200001];
int rv[200001];

struct maxtree {
	pair<int,int> tree[800001];
	// int lazy[200001];

	pair<int,int> maxi(pair<int,int> a, pair<int,int> b) {
		if (a.s == b.s) {
			if (a.f <= b.f) {
				return a;
			} else {
				return b;
			}
		} else {
			if (a.s >= b.s) {
				return a;
			} else {
				return b;
			}
		}
	}

	void build(int n, int a, int b) {
		if (a == b) {
			tree[n] = {rv[a],to[a]};
			return;
		}
		build(2*n,a,(a+b)/2);
		build(2*n+1,(a+b)/2+1,b);
		tree[n] = maxi(tree[2*n],tree[2*n+1]);
		return;
	}
	// void upd(int n, int a, int b, int x, int y, int val) {
	// 	if (lazy[n] != 0) {
	// 		// printf("[%d,%d]: %lld\n",a,b,lazy[n]);
	// 		tree[n] += lazy[n];
	// 		if (a != b) {
	// 			lazy[2*n] += lazy[n];
	// 			lazy[2*n+1] += lazy[n];
	// 		}
	// 		lazy[n] = 0;
	// 	}
	// 	if (a > b || b < x || y < a) {
	// 		return;
	// 	}
	// 	if (x <= a && b <= y) {
	// 		tree[n] += val;
	// 		// printf("!!!!!%d %d => %lld + %lld = %lld\n",a,b,tree[n]-val,val,tree[n]);
	// 		if (a != b) {
	// 			lazy[2*n] += val;
	// 			lazy[2*n+1] += val;
	// 		}
	// 		return;
	// 	}
	// 	upd(2*n,a,(a+b)/2,x,y,val);
	// 	upd(2*n+1,(a+b)/2+1,b,x,y,val);
	// 	tree[n] = max(tree[2*n],tree[2*n+1]);
	// 	return;
	// }
	pair<int,int> qry(int n, int a, int b, int x, int y) {
		// if (lazy[n] != 0) {
		// 	// printf("[%d,%d]: %lld\n",a,b,lazy[n]);
		// 	tree[n] += lazy[n];
		// 	if (a != b) {
		// 		lazy[2*n] += lazy[n];
		// 		lazy[2*n+1] += lazy[n];
		// 	}
		// 	lazy[n] = 0;
		// }
		if (a > b || b < x || y < a) {
			return {1e9,-1e9};
		}
		if (x <= a && b <= y) {
			// printf("%d %d %lld!\n",a,b,tree[n]);
			return tree[n];
		}
		return maxi(qry(2*n,a,(a+b)/2,x,y),qry(2*n+1,(a+b)/2+1,b,x,y));
	}
};

struct mintree {
	pair<int,int> tree[800001];

	pair<int,int> mini(pair<int,int> a, pair<int,int> b) {
		if (a.f == b.f) {
			if (a.s >= b.s) {
				return a;
			} else {
				return b;
			}
		} else {
			if (a.f <= b.f) {
				return a;
			} else {
				return b;
			}
		}
	}

	void build(int n, int a, int b) {
		if (a == b) {
			tree[n] = {rv[a],to[a]};
			return;
		}
		build(2*n,a,(a+b)/2);
		build(2*n+1,(a+b)/2+1,b);
		tree[n] = mini(tree[2*n],tree[2*n+1]);
		return;
	}
	// void upd(int n, int a, int b, int x, int y, int val) {
	// 	if (lazy[n] != 0) {
	// 		// printf("[%d,%d]: %lld\n",a,b,lazy[n]);
	// 		tree[n] += lazy[n];
	// 		if (a != b) {
	// 			lazy[2*n] += lazy[n];
	// 			lazy[2*n+1] += lazy[n];
	// 		}
	// 		lazy[n] = 0;
	// 	}
	// 	if (a > b || b < x || y < a) {
	// 		return;
	// 	}
	// 	if (x <= a && b <= y) {
	// 		tree[n] += val;
	// 		// printf("!!!!!%d %d => %lld + %lld = %lld\n",a,b,tree[n]-val,val,tree[n]);
	// 		if (a != b) {
	// 			lazy[2*n] += val;
	// 			lazy[2*n+1] += val;
	// 		}
	// 		return;
	// 	}
	// 	upd(2*n,a,(a+b)/2,x,y,val);
	// 	upd(2*n+1,(a+b)/2+1,b,x,y,val);
	// 	tree[n] = min(tree[2*n],tree[2*n+1]);
	// 	return;
	// }
	pair<int,int> qry(int n, int a, int b, int x, int y) {
		// if (lazy[n] != 0) {
		// 	// printf("[%d,%d]: %lld\n",a,b,lazy[n]);
		// 	tree[n] += lazy[n];
		// 	if (a != b) {
		// 		lazy[2*n] += lazy[n];
		// 		lazy[2*n+1] += lazy[n];
		// 	}
		// 	lazy[n] = 0;
		// }
		if (a > b || b < x || y < a) {
			return {1e9,-1e9};
		}
		if (x <= a && b <= y) {
			// printf("%d %d %lld!\n",a,b,tree[n]);
			return tree[n];
		}
		return mini(qry(2*n,a,(a+b)/2,x,y),qry(2*n+1,(a+b)/2+1,b,x,y));
	}
};

mintree tree1;
maxtree tree2;

queue<pair<int,int>> que;

int main() {
	int n;
	scanf("%d",&n);
	int max1 = 0;
	for (int i = 1; i <= n; ++i) {
		int l, r;
		scanf("%d%d",&l,&r);
		to[i] = r;
		rv[i] = l;
	}
	tree1.build(1,1,n);
	tree2.build(1,1,n);
	int q;
	scanf("%d",&q);
	for (int qi = 0; qi < q; ++qi) {
		int x;
		scanf("%d",&x);
		que.push({rv[x],to[x]});
		int ans = 0;
		int l = x;
		int r = x;
		int pl = l;
		int pr = r;
		while (que.size()) {
			int t = que.size();
			++ans;
			bool check = false;
			for (int i = 0; i < t; ++i) {
				int li, ri;
				tie(li,ri) = que.front();
				que.pop();
				// printf("%d %d <\n",li,ri);
				pair<int,int> nl = tree1.qry(1,1,n,li,ri);
				if (nl.f < l) {
					l = nl.f;
					que.push(nl);
				}
				pair<int,int> nr = tree2.qry(1,1,n,li,ri);
				if (nr.s > r) {
					r = nr.s;
					que.push(nr);
				}
				if (li == 1 && ri == n) {
					check = true;
					break;
				}
			}
			if (check)break;
			if (l == pl && r == pr)break;
			pl = l;
			pr = r;
		}
		while (que.size())que.pop();
		if (l != 1 || r != n)printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:174:6: warning: unused variable 'max1' [-Wunused-variable]
  174 |  int max1 = 0;
      |      ^~~~
passport.cpp:173:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
passport.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |   scanf("%d%d",&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~
passport.cpp:184:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
passport.cpp:187:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~

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