oj.uz

Submission #528678

# Submission time Handle Problem Language Result Execution time Memory
528678 2022-02-21T04:08:39 Z rk42745417 Railway Trip 2 (JOI22_ho_t4) C++17
27 / 100
 2000 ms 46644 KB 
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = ll(2e18) + ll(1e15);
const double EPS = 1e-8;
static int LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

const int LGN = 19, M = 2e5 + 25, N = 1e5 + 25;

pair<int, int> operator+(pair<int, int> a, pair<int, int> b) {
	return make_pair(min(a.first, b.first), max(a.second, b.second));
}
struct segtree {
	pair<int, int> arr[N << 1], tag[N];
	int n;
	void init(int _n) {
		n = _n;
		for(int i = 0; i < n * 2; i++)
			arr[i] = {INF, -INF};
		for(int i = 0; i < n; i++)
			tag[i] = {INF, -INF};
	}
	void upd(int p, pair<int, int> v) {
		arr[p] = arr[p] + v;
		if(p < n)
			tag[p] = tag[p] + v;
	}
	void push(int p) {
		for(int h = __lg(p); ~h; h--) {
			int i = p >> h;
			upd(i, tag[i >> 1]);
			upd(i ^ 1, tag[i >> 1]);
		}
	}
	void pull(int p) {
		for(; p > 1; p >>= 1)
			arr[p >> 1] = arr[p] + arr[p ^ 1] + tag[p >> 1];
	}
	void edt(int l, int r, int v) {
		int tl = l + n, tr = r + n - 1;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1)
				upd(l++, {v, -INF});
			if(r & 1)
				upd(--r, {v, -INF});
		}
		pull(tl); pull(tr);
	}
	void edt2(int l, int r, int v) {
		int tl = l + n, tr = r + n - 1;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1)
				upd(l++, {INF, v});
			if(r & 1)
				upd(--r, {INF, v});
		}
		pull(tl); pull(tr);
	}
	pair<int, int> que(int l, int r) {
		pair<int, int> res = {INF, -INF};
		push(l + n); push(r + n - 1);
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1)
				res = res + arr[l++];
			if(r & 1)
				res = res + arr[--r];
		}
		return res;
	}
} tree[LGN];

signed main() {
	int n, k, m;
	cin >> n >> k >> m;
	vector<pair<int, int>> arr(m);
	for(auto &[a, b] : arr)
		cin >> a >> b;

	for(int i = 0; i < LGN; i++)
		tree[i].init(n + 1);
	for(int i = 1; i <= n; i++)
		tree[0].edt(i, i + 1, i), tree[0].edt2(i, i + 1, i);
	for(const auto &[a, b] : arr) {
		if(a < b)
			tree[0].edt2(a, min(b + 1, a + k), b);
		else
			tree[0].edt(max(b, a - k + 1), a + 1, b);
	}
	for(int i = 1; i < LGN; i++) {
		for(int j = 1; j <= n; j++) {
			auto [l, r] = tree[i - 1].que(j, j + 1);
			auto [a, b] = tree[i - 1].que(l, r + 1);
			tree[i].edt(j, j + 1, a);
			tree[i].edt2(j, j + 1, b);
		}
	}

	auto in = [&](int t, auto inter) {
		return inter.first <= t && t <= inter.second;
	};

	int q;
	cin >> q;
	while(q--) {
		int s, t;
		cin >> s >> t;
		if(!in(t, tree[LGN - 1].que(s, s + 1)))
			cout << "-1\n";
		else {
			int res = 0;
			pair<int, int> owo = {s, s};
			for(int i = LGN - 1; ~i; i--)
				if(!in(t, tree[i].que(owo.first, owo.second + 1)))
					owo = tree[i].que(owo.first, owo.second + 1), res |= 1 << i;
			cout << res + 1 << '\n';
		}

	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44932 KB Output is correct
2 Correct 23 ms 44884 KB Output is correct
3 Correct 22 ms 44944 KB Output is correct
4 Correct 21 ms 44920 KB Output is correct
5 Correct 22 ms 44908 KB Output is correct
6 Correct 22 ms 44948 KB Output is correct
7 Correct 22 ms 44884 KB Output is correct
8 Correct 22 ms 44876 KB Output is correct
9 Correct 22 ms 44824 KB Output is correct
10 Correct 18 ms 44856 KB Output is correct
11 Correct 25 ms 44876 KB Output is correct
12 Correct 22 ms 44876 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44932 KB Output is correct
2 Correct 23 ms 44884 KB Output is correct
3 Correct 22 ms 44944 KB Output is correct
4 Correct 21 ms 44920 KB Output is correct
5 Correct 22 ms 44908 KB Output is correct
6 Correct 22 ms 44948 KB Output is correct
7 Correct 22 ms 44884 KB Output is correct
8 Correct 22 ms 44876 KB Output is correct
9 Correct 22 ms 44824 KB Output is correct
10 Correct 18 ms 44856 KB Output is correct
11 Correct 25 ms 44876 KB Output is correct
12 Correct 22 ms 44876 KB Output is correct
13 Correct 48 ms 44940 KB Output is correct
14 Correct 46 ms 44900 KB Output is correct
15 Correct 38 ms 44876 KB Output is correct
16 Correct 38 ms 44948 KB Output is correct
17 Correct 44 ms 44912 KB Output is correct
18 Correct 45 ms 44928 KB Output is correct
19 Correct 43 ms 44960 KB Output is correct
20 Correct 44 ms 44952 KB Output is correct
21 Correct 38 ms 44940 KB Output is correct
22 Correct 45 ms 44936 KB Output is correct
23 Correct 46 ms 44948 KB Output is correct
24 Correct 43 ms 44832 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1490 ms 45516 KB Output is correct
2 Correct 1467 ms 45516 KB Output is correct
3 Correct 1511 ms 45632 KB Output is correct
4 Correct 1498 ms 45516 KB Output is correct
5 Correct 1493 ms 46412 KB Output is correct
6 Correct 1489 ms 46404 KB Output is correct
7 Correct 1465 ms 46412 KB Output is correct
8 Correct 1422 ms 45644 KB Output is correct
9 Correct 1434 ms 45644 KB Output is correct
10 Correct 1484 ms 46412 KB Output is correct
11 Correct 1495 ms 46412 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1990 ms 45688 KB Output is correct
2 Correct 1508 ms 46632 KB Output is correct
3 Correct 1991 ms 45976 KB Output is correct
4 Correct 1795 ms 46500 KB Output is correct
5 Correct 1750 ms 46500 KB Output is correct
6 Correct 1730 ms 46496 KB Output is correct
7 Correct 1834 ms 46644 KB Output is correct
8 Execution timed out 2017 ms 46632 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1549 ms 46624 KB Output is correct
2 Execution timed out 2101 ms 45916 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44932 KB Output is correct
2 Correct 23 ms 44884 KB Output is correct
3 Correct 22 ms 44944 KB Output is correct
4 Correct 21 ms 44920 KB Output is correct
5 Correct 22 ms 44908 KB Output is correct
6 Correct 22 ms 44948 KB Output is correct
7 Correct 22 ms 44884 KB Output is correct
8 Correct 22 ms 44876 KB Output is correct
9 Correct 22 ms 44824 KB Output is correct
10 Correct 18 ms 44856 KB Output is correct
11 Correct 25 ms 44876 KB Output is correct
12 Correct 22 ms 44876 KB Output is correct
13 Correct 48 ms 44940 KB Output is correct
14 Correct 46 ms 44900 KB Output is correct
15 Correct 38 ms 44876 KB Output is correct
16 Correct 38 ms 44948 KB Output is correct
17 Correct 44 ms 44912 KB Output is correct
18 Correct 45 ms 44928 KB Output is correct
19 Correct 43 ms 44960 KB Output is correct
20 Correct 44 ms 44952 KB Output is correct
21 Correct 38 ms 44940 KB Output is correct
22 Correct 45 ms 44936 KB Output is correct
23 Correct 46 ms 44948 KB Output is correct
24 Correct 43 ms 44832 KB Output is correct
25 Correct 1490 ms 45516 KB Output is correct
26 Correct 1467 ms 45516 KB Output is correct
27 Correct 1511 ms 45632 KB Output is correct
28 Correct 1498 ms 45516 KB Output is correct
29 Correct 1493 ms 46412 KB Output is correct
30 Correct 1489 ms 46404 KB Output is correct
31 Correct 1465 ms 46412 KB Output is correct
32 Correct 1422 ms 45644 KB Output is correct
33 Correct 1434 ms 45644 KB Output is correct
34 Correct 1484 ms 46412 KB Output is correct
35 Correct 1495 ms 46412 KB Output is correct
36 Correct 1990 ms 45688 KB Output is correct
37 Correct 1508 ms 46632 KB Output is correct
38 Correct 1991 ms 45976 KB Output is correct
39 Correct 1795 ms 46500 KB Output is correct
40 Correct 1750 ms 46500 KB Output is correct
41 Correct 1730 ms 46496 KB Output is correct
42 Correct 1834 ms 46644 KB Output is correct
43 Execution timed out 2017 ms 46632 KB Time limit exceeded
44 Halted 0 ms 0 KB -