oj.uz

Submission #70546

# Submission time Handle Problem Language Result Execution time Memory
70546 2018-08-23T05:52:49 Z Just_Solve_The_Problem Railway Trip (JOI17_railway_trip) C++11
100 / 100
 378 ms 86716 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5 + 7;

int n, k, q;
pair < int, int > ar[20][N];
int a[N];

main() {
  scanf("%d %d %d", &n, &k, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  int que_st = 0;
  int stk[N];
  ar[0][1].first = 1;
  for (int i = 1; i <= n; i++) {
    while (que_st && a[stk[que_st]] <= a[i]) ar[0][stk[que_st--]].second = i;
    stk[++que_st] = i;
  }
  que_st = 0;
  ar[0][n].second = n;
  for (int i = n; i >= 1; i--) {
    while (que_st && a[stk[que_st]] <= a[i]) ar[0][stk[que_st--]].first = i;
    stk[++que_st] = i;
  }
  for (int i = 1; i < 20; i++) {
    for (int j = 1; j <= n; j++) {
      int x, y;
      tie(x, y) = ar[i - 1][j];
      ar[i][j] = make_pair(min(ar[i - 1][x].first, ar[i - 1][y].first), max(ar[i - 1][x].second, ar[i - 1][y].second));
    }
  }
  while (q--) {
    int l, r, ans = 0;
    scanf("%d %d", &l, &r);
    if (l > r) swap(l, r);
    int x, y;
    x = y = l;
    for (int i = 19; i >= 0; i--) {
      if (max(ar[i][x].second, ar[i][y].second) >= r) continue;
      tie(x, y) = make_pair(min(ar[i][x].first, ar[i][y].first), max(ar[i][x].second, ar[i][y].second));
      ans += (1 << i);
    }
    l = y;
    x = y = r;
    for (int i = 19; i >= 0; i--) {
      if (min(ar[i][x].first, ar[i][y].first) <= l) continue;
      tie(x, y) = make_pair(min(ar[i][x].first, ar[i][y].first), max(ar[i][x].second, ar[i][y].second));
      ans += (1 << i);
    }
    printf("%d\n", ans);
  }
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:12:8: 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:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
     ~~~~~^~~~~~~~~~~~~
railway_trip.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &l, &r);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 552 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 3 ms 620 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 836 KB Output is correct
2 Correct 33 ms 16780 KB Output is correct
3 Correct 40 ms 17180 KB Output is correct
4 Correct 41 ms 17304 KB Output is correct
5 Correct 35 ms 17632 KB Output is correct
6 Correct 37 ms 18108 KB Output is correct
7 Correct 40 ms 18580 KB Output is correct
8 Correct 33 ms 18840 KB Output is correct
9 Correct 31 ms 19480 KB Output is correct
10 Correct 29 ms 19812 KB Output is correct
11 Correct 38 ms 20480 KB Output is correct
12 Correct 41 ms 21064 KB Output is correct
13 Correct 42 ms 21636 KB Output is correct
14 Correct 41 ms 22200 KB Output is correct
15 Correct 37 ms 22788 KB Output is correct
16 Correct 39 ms 23264 KB Output is correct
17 Correct 38 ms 23796 KB Output is correct
18 Correct 45 ms 24380 KB Output is correct
19 Correct 32 ms 24968 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 27000 KB Output is correct
2 Correct 237 ms 28496 KB Output is correct
3 Correct 254 ms 29684 KB Output is correct
4 Correct 281 ms 31176 KB Output is correct
5 Correct 241 ms 32468 KB Output is correct
6 Correct 219 ms 33864 KB Output is correct
7 Correct 264 ms 35392 KB Output is correct
8 Correct 243 ms 36920 KB Output is correct
9 Correct 290 ms 38300 KB Output is correct
10 Correct 340 ms 39536 KB Output is correct
11 Correct 368 ms 40884 KB Output is correct
12 Correct 378 ms 42228 KB Output is correct
13 Correct 356 ms 43668 KB Output is correct
14 Correct 325 ms 44952 KB Output is correct
15 Correct 215 ms 46152 KB Output is correct
16 Correct 200 ms 47456 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 49228 KB Output is correct
2 Correct 205 ms 50852 KB Output is correct
3 Correct 213 ms 52564 KB Output is correct
4 Correct 220 ms 54164 KB Output is correct
5 Correct 356 ms 55752 KB Output is correct
6 Correct 282 ms 57564 KB Output is correct
7 Correct 327 ms 59412 KB Output is correct
8 Correct 257 ms 60884 KB Output is correct
9 Correct 274 ms 62572 KB Output is correct
10 Correct 344 ms 64392 KB Output is correct
11 Correct 290 ms 65996 KB Output is correct
12 Correct 314 ms 68008 KB Output is correct
13 Correct 286 ms 69620 KB Output is correct
14 Correct 296 ms 71568 KB Output is correct
15 Correct 280 ms 73240 KB Output is correct
16 Correct 264 ms 74980 KB Output is correct
17 Correct 271 ms 76644 KB Output is correct
18 Correct 262 ms 78464 KB Output is correct
19 Correct 265 ms 80080 KB Output is correct
20 Correct 193 ms 81688 KB Output is correct
21 Correct 184 ms 83296 KB Output is correct
22 Correct 166 ms 84992 KB Output is correct
23 Correct 185 ms 86716 KB Output is correct