# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
60421 |
2018-07-24T07:25:52 Z |
김세빈(#1743) |
Railway Trip (JOI17_railway_trip) |
C++11 |
|
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);
~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
14268 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |