oj.uz

Submission #866264

# Submission time Handle Problem Language Result Execution time Memory
866264 2023-10-25T16:36:45 Z fanwen Event Hopping (BOI22_events) C++17
20 / 100
 107 ms 17948 KB 
/**
 *      author : pham van sam 
 *      created : 25 October 2023 (Wednesday)
 **/

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
	#include "debug.h"
#else 
	#define clog if(false) cerr 
#endif

template < class T, T (*f) (T, T), T (*e) ()>
struct segment_tree {
    vector <T> it;
    int n;

    void update(int u, T p) {
        u += n - 1;
        it[u] = f(it[u], p);
        for(; u >>= 1; ) {
            it[u] = f(it[u << 1], it[u << 1 | 1]);
        }
    }

    void set(int u, T p) {
        u--;
        for (it[u += n] = p; u >>= 1; ) {
            it[u] = f(it[u << 1], it[u << 1 | 1]);
        }
    }

    T get(int p) {
        return it[p += n - 1];
    }

    T get(int l, int r) {
        l--;
        T resl = e(), resr = e();
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) resl = f(resl, it[l++]);
            if(r & 1) resr = f(it[--r], resr);
        }
        return f(resl, resr);
    }

    segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
        fill(it.begin(), it.end(), T{});
    }
};

pair <int, int> op(pair <int, int> a, pair <int, int> b) {

	if(a.first == 0) return b;
	if(b.first == 0) return a;
	return a < b ? a : b;
};

pair <int, int> e() {
	return make_pair(0, 0);
};

const int MAXN = 1e5 + 5;
const int LOG = 20;

struct segment {
	int l, r, ind;
	friend ostream & operator << (ostream &out, const segment &a) {
		return out << "(" << a.l << ", " << a.r << ", " << a.ind << ")";
	}
} A[MAXN];

int n, q, anc[MAXN][LOG], pos[MAXN];

void you_make_it(void) {
    cin >> n >> q;
    vector <int> compress;
    for (int i = 1; i <= n; ++i) {
    	cin >> A[i].l >> A[i].r;
    	A[i].ind = i;
    	compress.push_back(A[i].l);
    	compress.push_back(A[i].r);
    }
    sort(compress.begin(), compress.end());
    compress.erase(unique(compress.begin(), compress.end()), compress.end());

    for (int i = 1; i <= n; ++i) {
    	A[i].l = lower_bound(compress.begin(), compress.end(), A[i].l) - compress.begin() + 1;
    	A[i].r = lower_bound(compress.begin(), compress.end(), A[i].r) - compress.begin() + 1;
    }

    sort(A + 1, A + n + 1, [&] (const segment &a, const segment &b) -> bool {
    	return make_pair(a.l, a.r) < make_pair(b.l, b.r);
    });

    // for (int i = 1; i <= n; ++i) clog << debug(A[i]) << '\n';

    segment_tree <pair <int, int>, op, e> it((int) compress.size());

    for (int i = 1; i <= n; ++i) {
    	pos[A[i].ind] = i;
    	it.update(A[i].r, make_pair(A[i].l, i));
    	auto [_, id] = it.get(A[i].l, A[i].r);
    	anc[i][0] = id;

    	// clog << anc[i][0] << " \n"[i == 1];
    }

    for (int i = 1; i < LOG; ++i) {
    	for (int u = 1; u <= n; ++u) {
    		anc[u][i] = anc[anc[u][i - 1]][i - 1];
    	}
    }

    while(q--) {
    	int u, v; cin >> u >> v;
    	u = pos[u], v = pos[v];
    	if(u == v) {
    		cout << "0\n"; 
    		continue;
    	}
    	if(u > v) {
    		cout << "impossible\n";
    		continue;
    	}
    	if(A[u].r == A[v].r) {
    		cout << "1\n";
    		continue;
    	}

    	int ans = 0;
    	for (int i = LOG - 1; i >= 0; --i) {
    		if(A[u].r < A[anc[v][i]].l) {
    			ans += 1 << i;
    			v = anc[v][i];
    		}
    	}
    	if(A[v].l <= A[u].r && A[u].r <= A[v].r) ans++;
    	else {
    		v = anc[v][0];
    		ans += 2;
    	}
    	if(A[v].l <= A[u].r && A[u].r <= A[v].r) cout << ans;
    	else cout << "impossible";
    	cout << '\n';
    	// clog << u << " " << v << '\n';
    }
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

events.cpp: In instantiation of 'segment_tree<T, f, e>::segment_tree(int) [with T = std::pair<int, int>; T (* f)(T, T) = op; T (* e)() = e]':
events.cpp:101:67:   required from here
events.cpp:19:9: warning: 'segment_tree<std::pair<int, int>, op, e>::n' will be initialized after [-Wreorder]
   19 |     int n;
      |         ^
events.cpp:18:16: warning:   'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > segment_tree<std::pair<int, int>, op, e>::it' [-Wreorder]
   18 |     vector <T> it;
      |                ^~
events.cpp:50:5: warning:   when initialized here [-Wreorder]
   50 |     segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
      |     ^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 88 ms 16056 KB Output is correct
3 Correct 90 ms 15816 KB Output is correct
4 Correct 97 ms 16076 KB Output is correct
5 Correct 92 ms 16080 KB Output is correct
6 Correct 91 ms 16320 KB Output is correct
7 Correct 94 ms 16312 KB Output is correct
8 Incorrect 94 ms 17948 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4616 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 2 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4616 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 2 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4616 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 2 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 16060 KB Output is correct
2 Correct 94 ms 15936 KB Output is correct
3 Correct 93 ms 15820 KB Output is correct
4 Correct 91 ms 17856 KB Output is correct
5 Correct 94 ms 16328 KB Output is correct
6 Correct 107 ms 17596 KB Output is correct
7 Correct 104 ms 17704 KB Output is correct
8 Correct 100 ms 17848 KB Output is correct
9 Correct 87 ms 15784 KB Output is correct
10 Correct 98 ms 17356 KB Output is correct
11 Correct 104 ms 17092 KB Output is correct
12 Correct 103 ms 17328 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 88 ms 16056 KB Output is correct
3 Correct 90 ms 15816 KB Output is correct
4 Correct 97 ms 16076 KB Output is correct
5 Correct 92 ms 16080 KB Output is correct
6 Correct 91 ms 16320 KB Output is correct
7 Correct 94 ms 16312 KB Output is correct
8 Incorrect 94 ms 17948 KB Output isn't correct
9 Halted 0 ms 0 KB -