oj.uz

답안 #313455

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
313455 2020-10-16T03:35:55 Z VROOM_VARUN Railway Trip (JOI17_railway_trip) C++14
100 / 100
 364 ms 23684 KB 
/*
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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