Submission #706805

#	Time	Username	Problem	Language	Result	Execution time	Memory
706805		xuliu	Railway Trip 2 (JOI22_ho_t4)	C++17	71 / 100	801 ms	71716 KiB

Main

#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
• Subtask 2: 0 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 0 / 13