Submission #979075

#	Time	Username	Problem	Language	Result	Execution time	Memory
979075		temporary1	Passport (JOI23_passport)	C++17	6 / 100	59 ms	12892 KiB

passport

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

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

struct maxtree {
	int tree[800001];
	// int lazy[200001];
	void build(int n, int a, int b) {
		if (a == b) {
			tree[n] = to[a];
			return;
		}
		build(2*n,a,(a+b)/2);
		build(2*n+1,(a+b)/2+1,b);
		tree[n] = max(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;
	// }
	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 -1;
		}
		if (x <= a && b <= y) {
			// printf("%d %d %lld!\n",a,b,tree[n]);
			return tree[n];
		}
		return max(qry(2*n,a,(a+b)/2,x,y),qry(2*n+1,(a+b)/2+1,b,x,y));
	}
};

struct mintree {
	int tree[800001];
	// int lazy[200001];
	void build(int n, int a, int b) {
		if (a == b) {
			tree[n] = rv[a];
			return;
		}
		build(2*n,a,(a+b)/2);
		build(2*n+1,(a+b)/2+1,b);
		tree[n] = min(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;
	// }
	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;
		}
		if (x <= a && b <= y) {
			// printf("%d %d %lld!\n",a,b,tree[n]);
			return tree[n];
		}
		return min(qry(2*n,a,(a+b)/2,x,y),qry(2*n+1,(a+b)/2+1,b,x,y));
	}
};

mintree tree1;
maxtree tree2;

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);
		int l = rv[x];
		int r = to[x];
		int ans = 1;
		int cnt = 1;
		while (cnt++ <= n && (l != 1 || r != n)) {
			// printf("%d %d\n",l,r);
			int nl = tree1.qry(1,1,n,l,r);
			int nr = tree2.qry(1,1,n,l,r);
			l = nl;
			r = nr;
			++ans;
		}
		if (cnt > n)printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}

Compilation message (stderr)

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

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