oj.uz

Submission #979075

# Submission time Handle Problem Language Result Execution time Memory
979075 2024-05-10T07:40:53 Z temporary1 Passport (JOI23_passport) C++17
6 / 100
 59 ms 12892 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 29 ms 12888 KB Output is correct
5 Correct 29 ms 12892 KB Output is correct
6 Correct 59 ms 12892 KB Output is correct
7 Correct 28 ms 12884 KB Output is correct
8 Correct 45 ms 12884 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10756 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10744 KB Output is correct
7 Incorrect 2 ms 10588 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10756 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10744 KB Output is correct
7 Incorrect 2 ms 10588 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10756 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10744 KB Output is correct
7 Incorrect 2 ms 10588 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 29 ms 12888 KB Output is correct
5 Correct 29 ms 12892 KB Output is correct
6 Correct 59 ms 12892 KB Output is correct
7 Correct 28 ms 12884 KB Output is correct
8 Correct 45 ms 12884 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10756 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10744 KB Output is correct
15 Incorrect 2 ms 10588 KB Output isn't correct
16 Halted 0 ms 0 KB -