Submission #313455

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
313455	2020-10-16T03:35:55 Z	VROOM_VARUN	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	364 ms	23684 KB

railway_trip

/*
ID: varunra2
LANG: C++
TASK: railways
*/

#include<bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

const int siz = 20;
int n, k, q;

vector<VII> st;
VI vals;
VI prv;
VI nxt;

void init() {
  st.resize(n);
  vals.resize(n);
  prv.resize(n);
  nxt.resize(n);
  for(int i = 0; i < n; i++) {
    st[i].resize(siz);
  }
}

inline PII comb(PII a, int i) {
  // combining two ranges -> min of lefts/max of rights
  return MP(min(st[a.x][i].x, st[a.y][i].x), max(st[a.x][i].y, st[a.y][i].y));
}

pair<int, PII> qry(int ind, int l, int r) {
  // what is the longest range originating form ind, that is within range l -> r?
  // also what is the minimum # of steps we need to take to reach it

  pair<int, PII> ret = MP(0, MP(ind, ind));

  for(int i = siz - 1; i >= 0; i--) {
    PII cur = comb(ret.y, i);
    if(cur.x > l and cur.y < r) {
      ret.x += (1 << i);
      ret.y = cur;
    }
  }

  return ret;
}

int getDist(int a, int b) {
  if(a > b) swap(a, b); // answer will still stay the same, because graph is undirected

  auto ran1 = qry(a, -1, b); // without going into b's "territory", longest range
  auto ran2 = qry(b, ran1.y.y, n); // now in my territory

  return ran1.x + ran2.x + 1; // + 1 because you need to merge both ranges i think

}

void calcPrv() {
  // calculate previous greater or equal element index
  stack<int> s;

  for(int i = 0; i < n; i++) {
    while(!s.empty() and vals[s.top()] < vals[i]) s.pop();
    if(s.empty()) prv[i] = -1;
    else prv[i] = s.top();
    s.push(i);
  }

  prv[0] = 0;
}

void calcNxt() {
  // calculates next greater or equal element index

  stack<int> s;

  for(int i = n - 1; i >= 0; i--) {
    while(!s.empty() and vals[s.top()] < vals[i]) s.pop();
    if(s.empty()) nxt[i] = n;
    else nxt[i] = s.top();
    s.push(i);
  }

  nxt[n - 1] = n - 1;
}

int main() {
// #ifndef ONLINE_JUDGE
  // freopen("railways.in", "r", stdin);
  // freopen("railways.out", "w", stdout);
// #endif
  cin.sync_with_stdio(0); cin.tie(0);

  cin >> n >> k >> q;

  init();

  for(int i = 0; i < n; i++) {
    cin >> vals[i];
  }

  calcPrv();
  calcNxt();

  // for simple O(n ^ 2) solution, you can make an undirected unweighted graph out of prv/nxt, and answer is shortest path from a -> b

  for(int i = 0; i < n; i++) {
    st[i][0] = MP(prv[i], nxt[i]);
  }

  for(int j = 1; j < siz; j++) {
    for(int i = 0; i < n; i++) {
      st[i][j] = comb(st[i][j - 1], j - 1);
    }
  }

  while(q--) {
    int a, b;
    cin >> a >> b;
    a--, b--;

    cout << getDist(a, b) - 1 << '\n'; // minus one because ending node doesn't count
  }

  return 0;
}

Subtask #1

5.0 / 5.0

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

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	71 ms	21504 KB	Output is correct
3	Correct	73 ms	21376 KB	Output is correct
4	Correct	68 ms	21368 KB	Output is correct
5	Correct	67 ms	21504 KB	Output is correct
6	Correct	68 ms	21624 KB	Output is correct
7	Correct	68 ms	21684 KB	Output is correct
8	Correct	65 ms	21760 KB	Output is correct
9	Correct	78 ms	21928 KB	Output is correct
10	Correct	78 ms	21840 KB	Output is correct
11	Correct	74 ms	21888 KB	Output is correct
12	Correct	71 ms	21888 KB	Output is correct
13	Correct	73 ms	22008 KB	Output is correct
14	Correct	74 ms	21880 KB	Output is correct
15	Correct	73 ms	21888 KB	Output is correct
16	Correct	75 ms	21852 KB	Output is correct
17	Correct	67 ms	21748 KB	Output is correct
18	Correct	67 ms	21632 KB	Output is correct
19	Correct	66 ms	21632 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	231 ms	23032 KB	Output is correct
2	Correct	232 ms	23160 KB	Output is correct
3	Correct	221 ms	23032 KB	Output is correct
4	Correct	218 ms	23032 KB	Output is correct
5	Correct	216 ms	23032 KB	Output is correct
6	Correct	223 ms	23160 KB	Output is correct
7	Correct	212 ms	23180 KB	Output is correct
8	Correct	279 ms	23256 KB	Output is correct
9	Correct	342 ms	23216 KB	Output is correct
10	Correct	364 ms	23268 KB	Output is correct
11	Correct	350 ms	23216 KB	Output is correct
12	Correct	350 ms	23352 KB	Output is correct
13	Correct	346 ms	23216 KB	Output is correct
14	Correct	307 ms	23032 KB	Output is correct
15	Correct	243 ms	22904 KB	Output is correct
16	Correct	208 ms	22904 KB	Output is correct

Subtask #4

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	165 ms	23160 KB	Output is correct
2	Correct	161 ms	23160 KB	Output is correct
3	Correct	168 ms	23172 KB	Output is correct
4	Correct	169 ms	23032 KB	Output is correct
5	Correct	340 ms	23224 KB	Output is correct
6	Correct	287 ms	23512 KB	Output is correct
7	Correct	282 ms	23660 KB	Output is correct
8	Correct	290 ms	23344 KB	Output is correct
9	Correct	264 ms	23488 KB	Output is correct
10	Correct	259 ms	23616 KB	Output is correct
11	Correct	259 ms	23360 KB	Output is correct
12	Correct	260 ms	23576 KB	Output is correct
13	Correct	256 ms	23484 KB	Output is correct
14	Correct	283 ms	23616 KB	Output is correct
15	Correct	287 ms	23616 KB	Output is correct
16	Correct	285 ms	23620 KB	Output is correct
17	Correct	250 ms	23672 KB	Output is correct
18	Correct	266 ms	23684 KB	Output is correct
19	Correct	268 ms	23544 KB	Output is correct
20	Correct	211 ms	23288 KB	Output is correct
21	Correct	164 ms	23164 KB	Output is correct
22	Correct	164 ms	23160 KB	Output is correct
23	Correct	158 ms	23160 KB	Output is correct