oj.uz

답안 #1069867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069867 2024-08-22T09:29:48 Z 김은성(#11131) Passport (JOI23_passport) C++17
0 / 100
 2000 ms 90208 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) + 2);
		ret = min(ret, rangemin(1, 1, n, l, r));
	}
	else if(pl < l){
		int now = 0;
		while(pr <= r){
			if(pl >= l){
				return memo[((ll)l<<30) +r] = INF;
			}
			l = pl;
			pl = minquery(1, 1, n, l, r), pr = maxquery(1, 1, n, l, r);
			now++;
		}
		ret = min(ret, solve(pl, r)+now);
	}
	else if(pr > r)
		ret = min(ret, solve(l, pr) + 1);
	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:90:9: warning: unused variable 't' [-Wunused-variable]
   90 |  int q, t, i, j, k, x;
      |         ^
passport.cpp:90:15: warning: unused variable 'j' [-Wunused-variable]
   90 |  int q, t, i, j, k, x;
      |               ^
passport.cpp:90:18: warning: unused variable 'k' [-Wunused-variable]
   90 |  int q, t, i, j, k, x;
      |                  ^
passport.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
passport.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%d %d", &lb[i], &rb[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
passport.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 281 ms 19084 KB Output is correct
5 Execution timed out 2054 ms 90208 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 281 ms 19084 KB Output is correct
5 Execution timed out 2054 ms 90208 KB Time limit exceeded
6 Halted 0 ms 0 KB -