Submission #1309617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309617		thuhienne	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	384 ms	41116 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define thuhien ""
#define re exit(0);

const int maxm = 200009;
const int maxn = 100009;
const int LOG = 16;

inline pair <int,int> merge(pair <int,int> a,pair <int,int> b) {
	return {min(a.first,b.first),max(a.second,b.second)};
}

int n,k,m;
pair <int,int> line[maxm];
int q;

//segment tree
struct SegmentTree {
	pair <int,int> st[maxn * 4];
	
	void build(int id,int l,int r,pair <int,int> arr[]) {
		if (l == r) {
			st[id] = arr[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(id*2,l,mid,arr);
		build(id*2+1,mid+1,r,arr);
		st[id] = merge(st[id*2],st[id*2+1]);
	}
	pair <int,int> get(int id,int l,int r,int u,int v) {
		if (l >= u && r <= v) return st[id];
		
		int mid = (l + r) >> 1;
		
		if (v <= mid) return get(id*2,l,mid,u,v);
		else if (u > mid) return get(id*2+1,mid+1,r,u,v);
		
		return merge(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
	}
	
};

SegmentTree jump[LOG + 1];
pair <int,int> TEMP[maxn];

//create reach
pair <int,int> st[maxn * 4];

void add(int id,int l,int r,int u,int v,pair <int,int> val) {
	if (l > v || r < u) return;
	if (l >= u && r <= v) {
		st[id] = merge(st[id],val);
		return;	
	}
	int mid = (l + r) >> 1;
	add(id*2,l,mid,u,v,val);
	add(id*2+1,mid+1,r,u,v,val);
}
void dfs(int id,int l,int r) {
	if (l == r) {
		TEMP[l] = merge(st[id],{l,l});
		return;
	}
	int mid = (l + r) >> 1;
	st[id*2] = merge(st[id*2],st[id]);
	st[id*2+1] = merge(st[id*2+1],st[id]);
	dfs(id*2,l,mid);
	dfs(id*2+1,mid+1,r);
}


int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
	if (fopen(thuhien".inp","r")) {
	   freopen(thuhien".inp","r",stdin);
	   freopen(thuhien".out","w",stdout);
	}
	
	cin >> n >> k >> m;
	
	for (int i = 1;i <= 4*n;i++) st[i] = {1e9,-1e9};
	
	for (int i = 1;i <= m;i++) {
		cin >> line[i].first >> line[i].second;
		
		if (line[i].first < line[i].second) {
			add(1,1,n,line[i].first,min(line[i].first + k - 1,line[i].second - 1),{1e9,line[i].second});
		} else {
			add(1,1,n,max(line[i].first - k + 1,line[i].second + 1),line[i].first,{line[i].second,-1e9});
		}
		
	}
	
	dfs(1,1,n);
	
	jump[0].build(1,1,n,TEMP);
	for (int j = 1;j <= LOG;j++) {
		for (int i = 1;i <= n;i++) {
			
			pair <int,int> seg = jump[j - 1].get(1,1,n,i,i);
			TEMP[i] = jump[j - 1].get(1,1,n,seg.first,seg.second);
		
		}
		jump[j].build(1,1,n,TEMP);
	}
	
	cin >> q;
	while (q--) {
		int s,t;cin >> s >> t;
		
		int res = 0,l = s,r = s;
		for (int i = LOG;i >= 0;i--) {
			pair <int,int> damn = jump[i].get(1,1,n,l,r);
			if (damn.first > t || damn.second < t) {
				res += 1 << i;
				l = damn.first;
				r = damn.second;
			}
		}
		res++;
		
		cout << (res > n ? -1 : res) << '\n';
		
	}

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:81:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |            freopen(thuhien".inp","r",stdin);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:82:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |            freopen(thuhien".out","w",stdout);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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