oj.uz

답안 #60421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60421 2018-07-24T07:25:52 Z 김세빈(#1743) Railway Trip (JOI17_railway_trip) C++11
45 / 100
 1283 ms 14268 KB 
#include <bits/stdc++.h>

using namespace std;

vector <int> V[101010];
int D[101010], T[101010], I[22][101010];
int L[101010], CL[101010], R[101010], CR[101010];
int S[101010], sp;
int n, k, q;

void update(int p, int v)
{
	for(; p<=n; p+=p&-p) T[p] += v;
}

int get_sum(int p)
{
	int ret = 0;
	for(; p; p-=p&-p) ret += T[p];
	return ret;
}

int dist(int x, int a, int b)
{
	if(a == 0 || b == 0) return 1e8;
	if(a > b) swap(a, b);
	
	if(k > 20) return get_sum(b - 1) - get_sum(a);
	else return I[x][b] - I[x][a] - 1;
}

int main()
{
	int i, j, a, b, c, ans, s;
	int la, ra, lb, rb;
	int cla, cra, clb, crb;
	
	scanf("%d%d%d", &n, &k, &q);
	
	if(q > 50 && k > 20) return 0;
	
	for(i=1; i<=n; i++){
		scanf("%d ", D+i);
		V[D[i]].push_back(i);
	}
	
	for(i=1; i<=n; i++){
		c = 1;
		for(; sp && D[S[sp]] <= D[i]; ){
			if(D[S[sp]] < D[i]) sp --;
			if(D[S[sp]] == D[i]) c += CL[S[sp]], sp --;
		}
		if(sp) L[i] = S[sp], CL[i] = c;
		else CL[i] = 1e8;
		S[++sp] = i;
	}
	
	sp = 0;
	
	for(i=n; i>=1; i--){
		c = 1;
		for(; sp && D[S[sp]] <= D[i]; ){
			if(D[S[sp]] < D[i]) sp --;
			if(D[S[sp]] == D[i]) c += CR[S[sp]], sp --;
		}
		if(sp) R[i] = S[sp], CR[i] = c;
		else CR[i] = 1e8;
		S[++sp] = i;
	}
	
	if(k <= 20){
		for(i=1; i<=k; i++){
			s = 0;
			for(j=1; j<=n; j++){
				if(D[j] >= i) I[i][j] = ++s;
			}
		}
	}
	
	for(; q--; ){
		scanf("%d%d", &a, &b);
		
		la = ra = a; cla = cra = 0;
		lb = rb = b; clb = crb = 0;
		ans = 1e8;
		
		if(k > 20) for(i=1; i<=n; i++) update(i, 1);
		
		for(i=1; i<=k; i++){
			if(D[la] < i) cla += CL[la], la = L[la];
			if(D[ra] < i) cra += CR[ra], ra = R[ra];
			cla = min(cla, cra + 1);
			cra = min(cra, cla + 1);
			
			if(D[lb] < i) clb += CL[lb], lb = L[lb];
			if(D[rb] < i) crb += CR[rb], rb = R[rb];
			clb = min(clb, crb + 1);
			crb = min(crb, clb + 1);
			
			ans = min(ans, cla + clb + dist(i, la, lb));
			ans = min(ans, cra + clb + dist(i, ra, lb));
			ans = min(ans, cla + crb + dist(i, la, rb));
			ans = min(ans, cra + crb + dist(i, ra, rb));
			
			if(k > 20) for(int t: V[i]) update(t, -1);
		}
		
		printf("%d\n", ans);
	}
	
	return 0;
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d ", D+i);
   ~~~~~^~~~~~~~~~~~
railway_trip.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2788 KB Output is correct
3 Correct 5 ms 2788 KB Output is correct
4 Correct 6 ms 2864 KB Output is correct
5 Correct 6 ms 2940 KB Output is correct
6 Correct 5 ms 2940 KB Output is correct
7 Correct 5 ms 2940 KB Output is correct
8 Correct 7 ms 2940 KB Output is correct
9 Correct 4 ms 3016 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 3052 KB Output is correct
2 Correct 33 ms 9452 KB Output is correct
3 Correct 36 ms 13452 KB Output is correct
4 Correct 307 ms 13452 KB Output is correct
5 Correct 245 ms 13452 KB Output is correct
6 Correct 300 ms 13452 KB Output is correct
7 Correct 1283 ms 13452 KB Output is correct
8 Correct 461 ms 13452 KB Output is correct
9 Correct 806 ms 13452 KB Output is correct
10 Correct 322 ms 13452 KB Output is correct
11 Correct 971 ms 13452 KB Output is correct
12 Correct 677 ms 13452 KB Output is correct
13 Correct 542 ms 13452 KB Output is correct
14 Correct 833 ms 13452 KB Output is correct
15 Correct 615 ms 13452 KB Output is correct
16 Correct 465 ms 13452 KB Output is correct
17 Correct 609 ms 13452 KB Output is correct
18 Correct 628 ms 13452 KB Output is correct
19 Correct 707 ms 13452 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 13452 KB Output is correct
2 Correct 204 ms 13452 KB Output is correct
3 Correct 384 ms 13452 KB Output is correct
4 Correct 355 ms 13452 KB Output is correct
5 Correct 500 ms 13452 KB Output is correct
6 Correct 452 ms 13716 KB Output is correct
7 Correct 524 ms 14268 KB Output is correct
8 Correct 92 ms 14268 KB Output is correct
9 Correct 137 ms 14268 KB Output is correct
10 Correct 186 ms 14268 KB Output is correct
11 Correct 215 ms 14268 KB Output is correct
12 Correct 145 ms 14268 KB Output is correct
13 Correct 196 ms 14268 KB Output is correct
14 Correct 205 ms 14268 KB Output is correct
15 Correct 233 ms 14268 KB Output is correct
16 Correct 512 ms 14268 KB Output is correct

Subtask #4
0 / 55.0

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