oj.uz

Submission #60420

# Submission time Handle Problem Language Result Execution time Memory
60420 2018-07-24T07:24:13 Z 김세빈(#1743) Railway Trip (JOI17_railway_trip) C++11
20 / 100
 1369 ms 13436 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) 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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2788 KB Output is correct
3 Correct 6 ms 2824 KB Output is correct
4 Correct 5 ms 2900 KB Output is correct
5 Correct 7 ms 2976 KB Output is correct
6 Correct 6 ms 2976 KB Output is correct
7 Correct 5 ms 2976 KB Output is correct
8 Correct 5 ms 2976 KB Output is correct
9 Correct 5 ms 3068 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3068 KB Output is correct
2 Correct 29 ms 9500 KB Output is correct
3 Correct 42 ms 13436 KB Output is correct
4 Correct 297 ms 13436 KB Output is correct
5 Correct 248 ms 13436 KB Output is correct
6 Correct 248 ms 13436 KB Output is correct
7 Correct 1369 ms 13436 KB Output is correct
8 Correct 577 ms 13436 KB Output is correct
9 Correct 696 ms 13436 KB Output is correct
10 Correct 406 ms 13436 KB Output is correct
11 Correct 904 ms 13436 KB Output is correct
12 Correct 649 ms 13436 KB Output is correct
13 Correct 476 ms 13436 KB Output is correct
14 Correct 1045 ms 13436 KB Output is correct
15 Correct 651 ms 13436 KB Output is correct
16 Correct 523 ms 13436 KB Output is correct
17 Correct 755 ms 13436 KB Output is correct
18 Correct 739 ms 13436 KB Output is correct
19 Correct 938 ms 13436 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 13436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 13436 KB Output isn't correct
2 Halted 0 ms 0 KB -