oj.uz

답안 #1069631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069631 2024-08-22T07:31:20 Z 김은성(#11131) Passport (JOI23_passport) C++17
16 / 100
 2000 ms 198020 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll KEY = 1.557e8;
const int INF = 1.557e8;
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(l * KEY + 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)
		ret = min(ret, solve(pl, r) + 1);
	if(pr > r)
		ret = min(ret, solve(l, pr) + 1);
	ret = min(ret, rangemin(1, 1, n, l, r));
	return memo[l*KEY +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:77:9: warning: unused variable 't' [-Wunused-variable]
   77 |  int q, t, i, j, k, x;
      |         ^
passport.cpp:77:15: warning: unused variable 'j' [-Wunused-variable]
   77 |  int q, t, i, j, k, x;
      |               ^
passport.cpp:77:18: warning: unused variable 'k' [-Wunused-variable]
   77 |  int q, t, i, j, k, x;
      |                  ^
passport.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
passport.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   scanf("%d %d", &lb[i], &rb[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
passport.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1172 ms 47036 KB Output is correct
5 Execution timed out 2061 ms 128096 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4396 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 1 ms 4536 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 6 ms 4952 KB Output is correct
13 Correct 3 ms 4700 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Correct 9 ms 5212 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4396 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 1 ms 4536 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 6 ms 4952 KB Output is correct
13 Correct 3 ms 4700 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Correct 9 ms 5212 KB Output is correct
16 Correct 7 ms 4952 KB Output is correct
17 Correct 369 ms 33296 KB Output is correct
18 Correct 203 ms 17520 KB Output is correct
19 Correct 9 ms 9308 KB Output is correct
20 Execution timed out 2004 ms 198020 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4396 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 1 ms 4536 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 6 ms 4952 KB Output is correct
13 Correct 3 ms 4700 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Correct 9 ms 5212 KB Output is correct
16 Correct 7 ms 4952 KB Output is correct
17 Correct 369 ms 33296 KB Output is correct
18 Correct 203 ms 17520 KB Output is correct
19 Correct 9 ms 9308 KB Output is correct
20 Execution timed out 2004 ms 198020 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1172 ms 47036 KB Output is correct
5 Execution timed out 2061 ms 128096 KB Time limit exceeded
6 Halted 0 ms 0 KB -