Submission #532485

#	Time	Username	Problem	Language	Result	Execution time	Memory
532485		Haruto810198	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	876 ms	347872 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 = 100010;

int n, k, m, q;

// ST[0].l, r
vi evmin[MAX], evmax[MAX];
multiset<int> Smin, Smax;

struct SparseTable{
	int l[MAX], r[MAX];
	int stl[MAX][20], str[MAX][20];
	
	// build stl, str
	void build(){
		FOR(i, 1, n, 1){
			stl[i][0] = l[i];
			str[i][0] = r[i];
		}

		FOR(j, 1, 19, 1){
			FOR(i, 1, n, 1){
				int ii = i + (1<<(j-1));
				if(ii <= n){
					stl[i][j] = min(stl[i][j-1], stl[ii][j-1]);
					str[i][j] = max(str[i][j-1], str[ii][j-1]);
				}
				else{
					stl[i][j] = stl[i][j-1];
					str[i][j] = str[i][j-1];
				}
			}
		}
	}
	
	// query range min, max
	inline pii query(int ql, int qr){
		int rk = __lg(qr - ql + 1);
		return mkp(min(stl[ql][rk], stl[qr - (1<<rk) + 1][rk]), max(str[ql][rk], str[qr - (1<<rk) + 1][rk]));
	}
};

SparseTable ST[20];

void transition(int j){
	FOR(i, 1, n, 1){
		int ql = ST[j-1].l[i];
		int qr = ST[j-1].r[i];
		pii ans = ST[j-1].query(ql, qr);
		ST[j].l[i] = ans.F;
		ST[j].r[i] = ans.S;
	}
}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>k;

	// build ST[0].l, ST[0].r
	cin>>m;
	FOR(i, 1, m, 1){
		int from, to;
		int l, r;

		cin>>from>>to;
		if(from > to){
			// [from - k + 1, from], min -> to
			l = max(from - k + 1, to);
			r = from;
			evmin[l].pb(to);
			evmin[r+1].pb(-to);
		}
		else{
			// [from, from + k - 1], max -> to
			l = from;
			r = min(from + k - 1, to);
			evmax[l].pb(to);
			evmax[r+1].pb(-to);
		}
	}
	
	FOR(i, 1, n, 1){
		ST[0].l[i] = ST[0].r[i] = i;
	}

	FOR(i, 1, n, 1){
		for(int e : evmin[i]){
			if(e > 0) Smin.insert(e);
			else Smin.erase(Smin.find(-e));
		}

		for(int e : evmax[i]){
			if(e > 0) Smax.insert(e);
			else Smax.erase(Smax.find(-e));
		}

		if(!Smin.empty()) ST[0].l[i] = min(ST[0].l[i], *Smin.begin());
		if(!Smax.empty()) ST[0].r[i] = max(ST[0].r[i], *prev(Smax.end()));
	}
	
	/*
	cerr<<"ST[0] : "<<endl;
	cerr<<"<- : ";
	FOR(i, 1, n, 1){
		cerr<<ST[0].l[i]<<" ";
	}
	cerr<<endl;
	cerr<<"-> : ";
	FOR(i, 1, n, 1){
		cerr<<ST[0].r[i]<<" ";
	}
	cerr<<endl;
	*/
	
	// build ST[0] ~ ST[19]
	ST[0].build();
	FOR(j, 1, 19, 1){
		transition(j);
		ST[j].build();
	}

	// query
	cin>>q;
	while(q--){
		int qs, qt;
		cin>>qs>>qt;
		
		int res = 0;
		int lp = qs, rp = qs;
		pii nxt;

		for(int j = 19; j >= 0; j--){
			nxt = ST[j].query(lp, rp);
			if(!(nxt.F <= qt and qt <= nxt.S)){
				lp = nxt.F;
				rp = nxt.S;
				res += (1<<j);
			}
		}
		
		nxt = ST[0].query(lp, rp);
		if(!(lp <= qt and qt <= rp)){
			lp = nxt.F;
			rp = nxt.S;
			res += 1;
		}

		if(res > 1e6) res = -1;
		cout<<res<<'\n';
	}
	
	return 0;

}

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