Submission #532120

#	Time	Username	Problem	Language	Result	Execution time	Memory
532120		Haruto810198	Railway Trip 2 (JOI22_ho_t4)	C++17	0 / 100	634 ms	83860 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 200010;

struct Edge{
	int from, to;
	Edge (int _from, int _to) : from(_from), to(_to) {}
};

int n, k, m, q;
vector<Edge> el, er;
vector<vi> ln, rn;

bool cmp_by_from(Edge a, Edge b){
	if(a.from == b.from) return (a.to < b.to);
	return (a.from < b.from);
}

void build(vector<Edge>& edges, vector<vi>& nxt){
	
	// remove useless edges
	sort(edges.begin(), edges.end(), cmp_by_from);

	vector<Edge> tmp;
	for(Edge e : edges){
		if(tmp.empty()){
			tmp.pb(e);
		}
		else if(tmp.back().from == e.from){
			tmp.pop_back();
			tmp.pb(e);
		}
		else{
			tmp.pb(e);
		}
	}

	edges = tmp;
	
	// build binary jumping table
	int sz = szof(edges);
	int ptr = 0;
	
	nxt.resize(MAX);
	for(vi& V : nxt){
		V.resize(20);
	}

	FOR(i, 0, sz-1, 1){
		while(ptr < sz-1 and edges[ptr+1].from <= edges[i].to) ptr++;
		nxt[i][0] = ptr;
	}

	FOR(j, 1, 19, 1){
		FOR(i, 0, sz-1, 1){
			nxt[i][j] = nxt[ nxt[i][j-1] ][j-1];
		}
	}

}

int solve(int qfrom, int qto){
	vector<Edge> edges;
	vector<vi> nxt;
	int sz;
	int ret = 0;

	if(qfrom < 0){
		if(el.empty()) return INF;
		swap(edges, el);
		swap(nxt, ln);
	}
	else{
		if(er.empty()) return INF;
		swap(edges, er);
		swap(nxt, rn);
	}

	sz = szof(edges);
	
	// find first train
	if(qfrom < edges[0].from) ret += INF;

	int L = 0, R = sz-1, mid;
	while(L < R){
		mid = (L + R + 1) / 2;
		if(edges[mid].from <= qfrom) L = mid;
		else R = mid - 1;
	}
	int ptr = L;
	
	//cerr<<"first = "<<ptr<<", ";

	// binary jumping
	for(int j = 19; j >= 0; j--){
		if(edges[ nxt[ptr][j] ].to < qto){
			ptr = nxt[ptr][j];
			ret += (1<<j);
		}
	}

	if(edges[ptr].to < qto){
		ptr = nxt[ptr][0];
		ret++;
	}

	//cerr<<"jump = "<<ret<<endl;
	
	if(qfrom < 0){
		swap(edges, el);
		swap(nxt, ln);
	}
	else{
		swap(edges, er);
		swap(nxt, rn);
	}

	return ret;
}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>k;
	cin>>m;
	FOR(i, 1, m, 1){
		int _from, _to;
		cin>>_from>>_to;
		
		// <- : *= -1, ->
		if(_from < _to) er.pb(Edge(_from, _to));
		else el.pb(Edge(-_from, -_to));
	}
	
	build(el, ln);
	build(er, rn);
	
	cerr<<"el : "<<endl;
	for(Edge e : el){
		cerr<<e.from<<" "<<e.to<<endl;
	}
	cerr<<endl;
	cerr<<"er : "<<endl;
	for(Edge e : er){
		cerr<<e.from<<" "<<e.to<<endl;
	}
	cerr<<endl;

	cin>>q;
	FOR(i, 1, q, 1){
		
		int qfrom, qto;
		cin>>qfrom>>qto;
		if(qfrom > qto){
			qfrom *= -1;
			qto *= -1;
		}
		
		int res = solve(qfrom, qto) + 1;
		if(res > 1e6) res = -1;
		cout<<res<<'\n';
	}
	
	return 0;

}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13