Submission #594088

#	Time	Username	Problem	Language	Result	Execution time	Memory
594088		PoPularPlusPlus	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	798 ms	77520 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);

const int N = 200001;

struct item {
	int mx , mn;
};

struct Seg {
	ll siz = 1;
	vector<item> val;
	void init(int n){
		while(siz < n)siz*=2;
		
		val.resize(siz * 2);
		
	}
	
	item NutralElement = {-1 , N};
	
	item merge(item a , item b){
		return {max(a.mx , b.mx) , min(a.mn , b.mn)};
	}
	
	item single(pair<int,int> a){
		return {a.vf , a.vs};
	}
	
	void build(vector<pair<int,int>>& arr  , int x , int lx , int rx){
		if(rx-lx==1){
			if(lx < (int)arr.size()){
				val[x] = single(arr[lx]);
			}
			else val[x] = NutralElement;
			return;
		}
		int m = (lx + rx) / 2;
		build(arr , 2 * x + 1 , lx , m);
		build(arr, 2 * x + 2 , m , rx);
		val[x]=merge(val[2 * x + 1] , val[2 * x + 2]);
	}
	
	void build(vector<pair<int,int>>& arr){
		build(arr , 0 , 0 , siz);
	}
	
	item sum(int l , int r , int x , int lx , int rx){
		if(lx >= r  || l >= rx)return NutralElement;
		if(lx >= l && rx <= r)return val[x];
		int m = (lx + rx) / 2;
		item s1 = sum(l , r , 2 * x + 1 ,lx , m);
		item s2 = sum(l , r , 2 * x + 2, m , rx);
		return merge(s1,s2);
	}
	
	item sum(int l , int r){
		return sum(l , r , 0 , 0 , siz);
	}
	
};

void solve(){
	int n;
	cin >> n;
	int k;
	cin >> k;
	int m;
	cin >> m;
	int arr[m][2];
	for(int i = 0; i < m; i++){cin >> arr[i][0] >> arr[i][1]; arr[i][0]--,arr[i][1]--;}
	int L = 20;
	pair<int,int> range[n][L];
	Seg st[L];
	for(int i = 0; i < L; i++)
		st[i].init(n + 1);
	vector<pair<int,int>> v(n);
	int mx[n] , mn[n];
	set<pair<int,int> , greater<pair<int,int>>> s;
	vector<vector<int>> add(n+1) , remove(n+1);
	for(int i = 0; i < m; i++){
		if(arr[i][0] < arr[i][1]){
			add[arr[i][0]].pb(i);
			remove[min(arr[i][0] + k , arr[i][1])].pb(i);
		}
	}
	for(int i = 0; i < n; i++)mx[i] = mn[i] = i;
	for(int i = 0; i < n; i++){
		for(int j : add[i]){
			s.insert(mp(arr[j][1] , j));
		}
		for(int j : remove[i]){
			s.erase(mp(arr[j][1] , j));
		}
		if(s.size())
		mx[i] = (*(s.begin())).vf;
	}
	s.clear();
	for(int i = 0; i <= n; i++)add[i].clear(),remove[i].clear();
	for(int i = 0; i < m; i++){
		if(arr[i][0] > arr[i][1]){
			add[arr[i][0]].pb(i);
			remove[max(0,max(arr[i][0] - k + 1 , arr[i][1] + 1))].pb(i);
		}
	}
	set<pair<int,int>> s1;
	for(int i = n - 1; i >=0; i--){
		for(int j : add[i]){
			s1.insert(mp(arr[j][1] , j));
		}
		if(s1.size())
		mn[i] = (*(s1.begin())).vf;
		for(int j : remove[i]){
			s1.erase(mp(arr[j][1] , j));
		}
	}
	//for(int i = 0; i < n; i++)cout << mx[i] << ' ' << mn[i] << '\n';
	for(int j = 0; j < L; j++){
		for(int i = 0; i < n; i++){
			if(j == 0)v[i] = range[i][j] = mp(mx[i] , mn[i]);
			else {
				if(v[i].vf == N && v[i].vs == -1){
					range[i][j] = v[i];
					continue;
				}
				item it = st[j-1].sum(v[i].vs, v[i].vf + 1);
				v[i] = mp(it.mx , it.mn);
				range[i][j] = v[i];
			}
		}
		st[j].build(v);
	}
	int q;
	cin >> q;
	
	while(q--){
		int s2 , t;
		cin >> s2 >> t;
		s2--;
		t--;
		int ans = 0;
		int l = s2 , r = s2;
		for(int i = L - 1; i >= 0; i--){
			item it = st[i].sum(l,r+1);
			if(it.mx == r && it.mn == l){
				ans = -2;
				break;
			}
			if(it.mx >= t && it.mn <= t)continue;
			ans += (1 << i);
			l = min(l , it.mn);
			r = max(r , it.mx);
		}
		ans++;
		cout << ans << '\n';
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	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