oj.uz

Submission #706805

# Submission time Handle Problem Language Result Execution time Memory
706805 2023-03-07T19:07:16 Z xuliu Railway Trip 2 (JOI22_ho_t4) C++17
71 / 100
 801 ms 71716 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define debug if(0)

typedef pair<int, int> pii;
const pii ID = {0, 0};

pii comb(pii a, pii b) {
	if(a == ID) return b;
	if(b == ID) return a;
	int lx = min(a.first, b.first), rx = max(a.second, b.second);
	return {lx, rx};
}

struct segtree {
	int sz;
	vector<pii> seg;
	void init(int n, vector<pii> &v) {
		sz = 1;
		while(sz < n) sz <<= 1;
		seg.assign(2*sz+2, ID);
		for(int i=0; i<n; i++) seg[i+1+sz] = v[i];
		for(int i=sz-1; i>=1; i--) seg[i] = comb(seg[i<<1], seg[(i<<1)+1]);
	}
	pii query(int a, int b, int x, int l, int r) {
		if(b < l || a > r) return ID;
		if(a <= l && b >= r) return seg[x];
		int m = (l+r)>>1;
		return comb(query(a, b, x<<1, l, m), query(a, b, (x<<1)+1, m+1, r));
	}
	pii query(int a, int b) { return query(a, b, 1, 0, sz-1); }
};

const int N = 1e5 + 4, M = 20;
pii range[M][N];
vector<int> ev[N];
segtree st[M];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, k; cin>>n>>k;
	int m; cin>>m;
	vector<pii> lines;
	for(int i=0; i<m; i++) {
		int a, b; cin>>a>>b;
		lines.push_back({a, b});
		if(a < b) {
			ev[a].push_back(b);
			ev[min(b+1, a+k)].push_back(-b);
		}
		else {
			ev[max(b, a-k+1)].push_back(b);
			ev[a+1].push_back(-b);
		}
	}
	for(int i=0; i<=n; i++) range[0][i] = {i, i};
	multiset<int> S;
	for(int i=1; i<=n; i++) {
		for(auto e : ev[i]) {
			if(e > 0) S.insert(e);
			else {
				auto it = S.find(-e);
				if(it != S.end()) S.erase(it);
			}
		}
		if(!S.empty()) {
			auto it = S.end(); --it;
			range[0][i] = {min(i, *S.begin()), max(i, *it)};
		}
	}
	debug {
		for(int i=1; i<=n; i++) {
			cerr<<"range[0]["<<i<<"] = {"<<range[0][i].first<<", "<<range[0][i].second<<"}\n";
		}
	}
	{
		vector<pii> vv;
		for(int i=1; i<=n; i++) vv.push_back(range[0][i]);
		st[0].init(n, vv);
	}
	for(int j=1; j<M; j++) {
		vector<pii> vv;
		for(int i=1; i<=n; i++) {
			int l = range[j-1][i].first, r = range[j-1][i].second;
			range[j][i] = st[j-1].query(l, r);
			vv.push_back(range[j][i]);
		}
		st[j].init(n, vv);
	}
	
	int q; cin>>q;
	while(q--) {
		int s, t; cin>>s>>t;
		if(t < range[M-1][s].first || t > range[M-1][s].second) {
			cout<<"-1\n";
			continue;
		}
		int ans = 0;
		pii r = {s, s};
		for(int j=M-1; j>=0; j--) {
			pii tt = st[j].query(r.first, r.second);
			if(t < tt.first || t > tt.second) {
				r = tt;
				ans += (1<<j);
			}
		}
		cout<<ans+1<<"\n";
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2940 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 2 ms 2912 KB Output is correct
5 Correct 3 ms 2900 KB Output is correct
6 Correct 3 ms 2988 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Incorrect 2 ms 2772 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2940 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 2 ms 2912 KB Output is correct
5 Correct 3 ms 2900 KB Output is correct
6 Correct 3 ms 2988 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Incorrect 2 ms 2772 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 64992 KB Output is correct
2 Correct 420 ms 65128 KB Output is correct
3 Correct 465 ms 65308 KB Output is correct
4 Correct 423 ms 64900 KB Output is correct
5 Correct 497 ms 68480 KB Output is correct
6 Correct 437 ms 66128 KB Output is correct
7 Correct 485 ms 71716 KB Output is correct
8 Correct 411 ms 66516 KB Output is correct
9 Correct 459 ms 66916 KB Output is correct
10 Correct 438 ms 67228 KB Output is correct
11 Correct 443 ms 67168 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 66056 KB Output is correct
2 Correct 482 ms 68740 KB Output is correct
3 Correct 586 ms 65380 KB Output is correct
4 Correct 595 ms 71644 KB Output is correct
5 Correct 615 ms 70272 KB Output is correct
6 Correct 665 ms 70212 KB Output is correct
7 Correct 592 ms 67208 KB Output is correct
8 Correct 677 ms 67276 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 69236 KB Output is correct
2 Correct 801 ms 65324 KB Output is correct
3 Correct 763 ms 63460 KB Output is correct
4 Correct 662 ms 62160 KB Output is correct
5 Correct 537 ms 61764 KB Output is correct
6 Correct 608 ms 61232 KB Output is correct
7 Correct 564 ms 70476 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 11 ms 3848 KB Output is correct
10 Correct 521 ms 68792 KB Output is correct
11 Correct 654 ms 70244 KB Output is correct
12 Correct 699 ms 69008 KB Output is correct
13 Correct 681 ms 70100 KB Output is correct
14 Correct 3 ms 2900 KB Output is correct
15 Correct 11 ms 3864 KB Output is correct
16 Correct 519 ms 67256 KB Output is correct
17 Correct 776 ms 67232 KB Output is correct
18 Correct 752 ms 67176 KB Output is correct
19 Correct 693 ms 67296 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2940 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 2 ms 2912 KB Output is correct
5 Correct 3 ms 2900 KB Output is correct
6 Correct 3 ms 2988 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Incorrect 2 ms 2772 KB Output isn't correct
11 Halted 0 ms 0 KB -