oj.uz

Submission #706804

# Submission time Handle Problem Language Result Execution time Memory
706804 2023-03-07T19:05:57 Z xuliu Railway Trip 2 (JOI22_ho_t4) C++17
71 / 100
 720 ms 70936 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 = 19;
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 3 ms 2900 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 3 ms 2932 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 3 ms 2976 KB Output is correct
6 Correct 2 ms 2900 KB Output is correct
7 Correct 3 ms 2932 KB Output is correct
8 Correct 2 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 3 ms 2900 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 3 ms 2932 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 3 ms 2976 KB Output is correct
6 Correct 2 ms 2900 KB Output is correct
7 Correct 3 ms 2932 KB Output is correct
8 Correct 2 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 400 ms 62832 KB Output is correct
2 Correct 384 ms 62860 KB Output is correct
3 Correct 436 ms 63468 KB Output is correct
4 Correct 372 ms 62716 KB Output is correct
5 Correct 461 ms 67756 KB Output is correct
6 Correct 404 ms 65376 KB Output is correct
7 Correct 452 ms 70920 KB Output is correct
8 Correct 413 ms 64612 KB Output is correct
9 Correct 399 ms 64956 KB Output is correct
10 Correct 419 ms 66572 KB Output is correct
11 Correct 419 ms 66408 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 64488 KB Output is correct
2 Correct 456 ms 68444 KB Output is correct
3 Correct 564 ms 63812 KB Output is correct
4 Correct 565 ms 70936 KB Output is correct
5 Correct 584 ms 69824 KB Output is correct
6 Correct 587 ms 69740 KB Output is correct
7 Correct 554 ms 66816 KB Output is correct
8 Correct 642 ms 66608 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 68952 KB Output is correct
2 Correct 700 ms 63768 KB Output is correct
3 Correct 693 ms 61164 KB Output is correct
4 Correct 645 ms 59528 KB Output is correct
5 Correct 513 ms 58916 KB Output is correct
6 Correct 538 ms 58560 KB Output is correct
7 Correct 546 ms 69040 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 10 ms 3796 KB Output is correct
10 Correct 525 ms 67792 KB Output is correct
11 Correct 586 ms 69900 KB Output is correct
12 Correct 602 ms 68792 KB Output is correct
13 Correct 639 ms 70032 KB Output is correct
14 Correct 3 ms 2932 KB Output is correct
15 Correct 11 ms 3796 KB Output is correct
16 Correct 417 ms 66400 KB Output is correct
17 Correct 720 ms 66644 KB Output is correct
18 Correct 678 ms 66680 KB Output is correct
19 Correct 652 ms 66712 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2900 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 3 ms 2932 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 3 ms 2976 KB Output is correct
6 Correct 2 ms 2900 KB Output is correct
7 Correct 3 ms 2932 KB Output is correct
8 Correct 2 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 -