oj.uz

Submission #805338

# Submission time Handle Problem Language Result Execution time Memory
805338 2023-08-03T15:27:12 Z thimote75 Railway Trip (JOI17_railway_trip) C++14
100 / 100
 500 ms 27280 KB 
#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

struct Container {
    map<int, int> m;

    void insert(int height, int pos) {
        auto it = m.upper_bound(height);
        while (it != m.begin()) {
            it --;

            int h = (*it).first;
            m.erase(h);
            
            it = m.upper_bound(height);
        }

        m.insert({ height, pos });
    }

    int query (int height) {
        auto it = m.lower_bound(height);
        if (it == m.end()) return -1;

        return (*it).second;
    }
};

idata heights;

idata  left_road;
idata right_road;

igrid  left_road_2k;
igrid right_road_2k;

int N, K, Q;

const int MAXK = 20;

bool intersects (pair<int, int> a, pair<int, int> b) {
    if (b < a) swap (a, b);

    return a.second >= b.first;
}
pair<int, int> create (pair<int, int> start, int k) {
    int l = start.first;
    int r = start.second;

    int nl = min(
        left_road_2k[l][k],
        left_road_2k[r][k]
    );
    int nr = max(
        right_road_2k[l][k],
        right_road_2k[r][k]
    );

    return { nl, nr };
}

pair<pair<int, int>, int> jump_until (pair<int, int> start, pair<int, int> other) {
    int count = 0;
    for (int k = MAXK - 1; k >= 0; k --) {
        pair<int, int> potential = create(start, k);
        if (intersects(potential, other)) continue ;

        start = potential;
        count += 1 << k;
    }

    return { start, count };
}

void blf () {
    left_road_2k .resize(N, idata(MAXK, 0));
    right_road_2k.resize(N, idata(MAXK, N - 1));

    for (int i = 0; i < N; i ++) {
         left_road_2k[i][0] =  left_road[i];
        right_road_2k[i][0] = right_road[i];
    }

    for (int k = 0; k + 1 < MAXK; k ++) {
        for (int i = 0; i < N; i ++) {
            left_road_2k[i][k + 1] = min(
                left_road_2k[ left_road_2k[i][k]][k],
                left_road_2k[right_road_2k[i][k]][k]
            );
            right_road_2k[i][k + 1] = max(
                right_road_2k[ left_road_2k[i][k]][k],
                right_road_2k[right_road_2k[i][k]][k]
            );
        }
    }
}

idata bfs (int start) {
    queue<int> q; 
    idata answer(N, 1e9);
    answer[start] = 0;
    q.push(start);

    while (q.size() != 0) {
        int curr = q.front(); q.pop();

        for (int next : { left_road[curr], right_road[curr] }) {
            if (next == -1) continue ;

            if (answer[next] != 1e9) continue ;
            q.push(next);
            answer[next] = answer[curr] + 1;
        }
    }

    return answer;
}

int main () {
    cin >> N >> K >> Q;

    heights.resize(N);
    for (int i = 0; i < N; i ++) cin >> heights[i];

    left_road.resize(N, -1);
    Container cnt;
    for (int i = 0; i < N; i ++) {
        left_road[i] = cnt.query(heights[i]);
        if (i == 0) left_road[i] = 0;

        cnt.insert(heights[i], i);
    }

    cnt.m.clear();
    right_road.resize(N, -1);
    for (int i = N - 1; i >= 0; i --) {
        right_road[i] = cnt.query(heights[i]);
        if (i + 1 == N) right_road[i] = i;

        cnt.insert(heights[i], i);
    }

    blf();
    
    for (int q = 0; q < Q; q ++) {
        int a, b;
        cin >> a >> b;
        a --; b --;

        if (a > b) swap(a, b);

        const auto data1 = jump_until({ a, a }, { b, b });
        const auto data2 = jump_until({ b, b }, data1.first);
        
        cout << data1.second + data2.second << "\n";
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 70 ms 25156 KB Output is correct
3 Correct 76 ms 25204 KB Output is correct
4 Correct 71 ms 25172 KB Output is correct
5 Correct 66 ms 25188 KB Output is correct
6 Correct 69 ms 25292 KB Output is correct
7 Correct 76 ms 25464 KB Output is correct
8 Correct 72 ms 25144 KB Output is correct
9 Correct 107 ms 25464 KB Output is correct
10 Correct 105 ms 25252 KB Output is correct
11 Correct 93 ms 25464 KB Output is correct
12 Correct 93 ms 25372 KB Output is correct
13 Correct 106 ms 25380 KB Output is correct
14 Correct 92 ms 25388 KB Output is correct
15 Correct 113 ms 25468 KB Output is correct
16 Correct 94 ms 25444 KB Output is correct
17 Correct 91 ms 25364 KB Output is correct
18 Correct 76 ms 25360 KB Output is correct
19 Correct 79 ms 25408 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 26864 KB Output is correct
2 Correct 378 ms 26764 KB Output is correct
3 Correct 331 ms 26732 KB Output is correct
4 Correct 303 ms 26828 KB Output is correct
5 Correct 372 ms 26800 KB Output is correct
6 Correct 399 ms 26784 KB Output is correct
7 Correct 326 ms 26772 KB Output is correct
8 Correct 431 ms 26860 KB Output is correct
9 Correct 500 ms 26872 KB Output is correct
10 Correct 465 ms 26852 KB Output is correct
11 Correct 479 ms 26828 KB Output is correct
12 Correct 449 ms 26808 KB Output is correct
13 Correct 459 ms 26852 KB Output is correct
14 Correct 411 ms 26800 KB Output is correct
15 Correct 374 ms 26788 KB Output is correct
16 Correct 306 ms 26720 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 26596 KB Output is correct
2 Correct 289 ms 26968 KB Output is correct
3 Correct 313 ms 26872 KB Output is correct
4 Correct 294 ms 26924 KB Output is correct
5 Correct 444 ms 26820 KB Output is correct
6 Correct 414 ms 27180 KB Output is correct
7 Correct 407 ms 27280 KB Output is correct
8 Correct 411 ms 27064 KB Output is correct
9 Correct 394 ms 27116 KB Output is correct
10 Correct 368 ms 27172 KB Output is correct
11 Correct 370 ms 27244 KB Output is correct
12 Correct 362 ms 27172 KB Output is correct
13 Correct 365 ms 27160 KB Output is correct
14 Correct 430 ms 27192 KB Output is correct
15 Correct 421 ms 27184 KB Output is correct
16 Correct 450 ms 27140 KB Output is correct
17 Correct 440 ms 27148 KB Output is correct
18 Correct 362 ms 27140 KB Output is correct
19 Correct 423 ms 27180 KB Output is correct
20 Correct 351 ms 27140 KB Output is correct
21 Correct 286 ms 26968 KB Output is correct
22 Correct 332 ms 26920 KB Output is correct
23 Correct 278 ms 26952 KB Output is correct