oj.uz

Submission #1069850

# Submission time Handle Problem Language Result Execution time Memory
1069850 2024-08-22T09:23:48 Z 김은성(#11131) Passport (JOI23_passport) C++17
0 / 100
 2000 ms 92528 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll KEY = 1.557e8;
const int INF = 1.557e8;
unordered_map<ll, int> memo;
int lb[200009], rb[200009];
int n, minl[1<<19], maxr[1<<19];
int tree[1<<19];
void update(int v, int l, int r, int idx, int val){
	if(l==r)
		tree[v] = val;
	else{
		int mid = (l+r)/2;
		if(idx <= mid)
			update(2*v, l, mid, idx, val);
		else
			update(2*v+1, mid+1, r, idx, val);
		tree[v] = min(tree[2*v], tree[2*v+1]);
	}
}
int rangemin(int v, int l, int r, int s, int e){
	if(e<l || r<s)
		return INF;
	if(s<=l && r<=e)
		return tree[v];
	int mid = (l+r)/2;
	return min(rangemin(2*v, l, mid, s, e), rangemin(2*v+1, mid+1, r, s, e));
}
void settree(int v, int l, int r){
	if(l==r){
		minl[v] = lb[l];
		maxr[v] = rb[l];
	}
	else{
		int mid = (l+r)/2;
		settree(2*v, l, mid);
		settree(2*v+1, mid+1, r);
		minl[v] = min(minl[2*v], minl[2*v+1]);
		maxr[v] = max(maxr[2*v], maxr[2*v+1]);
	}
}
int minquery(int v, int l, int r, int s, int e){
	if(e<l || r<s)
		return INF;
	if(s<=l && r<=e)
		return minl[v];
	int mid = (l+r)/2;
	return min(minquery(2*v, l, mid, s, e), minquery(2*v+1, mid+1, r, s, e));
}
int maxquery(int v, int l, int r, int s, int e){
	if(e<l || r<s)
		return -1;
	if(s<=l && r<=e)
		return maxr[v];
	int mid = (l+r)/2;
	return max(maxquery(2*v, l, mid, s, e), maxquery(2*v+1, mid+1, r, s, e));
}
int solve(int l, int r){
	if(l==1 && r==n)
		return 0;
	auto it = memo.find(((ll)l<<30) + r);
	if(it != memo.end())
		return it->second;
	int pl = minquery(1, 1, n, l, r), pr = maxquery(1, 1, n, l, r);
	//printf("l=%d r=%d pl=%d pr=%d\n",l, r, pl,pr);
	int ret = INF;
	if(pl < l && pr > r)
		ret = min(ret, solve(pl, pr) + 1);
	else if(pl < l)
		ret = min(ret, solve(pl, r) + 1);
	else if(pr > r)
		ret = min(ret, solve(l, pr) + 1);
	ret = min(ret, rangemin(1, 1, n, l, r));
	return memo[((ll)l<<30) +r] = ret;
}
int ans[200009];
int main(){
	int q, t, i, j, k, x;
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d %d", &lb[i], &rb[i]);
	}
	memset(tree, 127, sizeof(tree));
	settree(1,1, n);
	scanf("%d", &q);
	vector<int> vec;
	for(i=1; i<=n; i++)
		vec.push_back(i);
	sort(vec.begin(), vec.end(), [](int &u, int &v){return rb[v]-lb[v] < rb[u]-lb[u];});
	for(int u: vec){
		ans[u] = solve(lb[u], rb[u]) + 1;
		update(1, 1, n, u, ans[u]);
	}
	while(q--){
		scanf("%d", &x);
		if(ans[x] >= INF/2)
			ans[x] = -1;
		printf("%d\n", ans[x]);
	}
	return 0;
}

Compilation message

passport.cpp: In function 'int main()':
passport.cpp:79:9: warning: unused variable 't' [-Wunused-variable]
   79 |  int q, t, i, j, k, x;
      |         ^
passport.cpp:79:15: warning: unused variable 'j' [-Wunused-variable]
   79 |  int q, t, i, j, k, x;
      |               ^
passport.cpp:79:18: warning: unused variable 'k' [-Wunused-variable]
   79 |  int q, t, i, j, k, x;
      |                  ^
passport.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
passport.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d %d", &lb[i], &rb[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
passport.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 317 ms 21624 KB Output is correct
5 Execution timed out 2007 ms 92528 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8632 KB Output is correct
7 Incorrect 2 ms 8540 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 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8632 KB Output is correct
7 Incorrect 2 ms 8540 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 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8632 KB Output is correct
7 Incorrect 2 ms 8540 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 317 ms 21624 KB Output is correct
5 Execution timed out 2007 ms 92528 KB Time limit exceeded
6 Halted 0 ms 0 KB -