Submission #535170

#	Time	Username	Problem	Language	Result	Execution time	Memory
535170		victor_gao	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	1527 ms	191028 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
//#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
struct Node{
	int mx,mn;
	void pull(Node a,Node b){
		mx=max(a.mx,b.mx);
		mn=min(a.mn,b.mn);
	}
};
struct segment_tree{
	Node seg[4*N],tag[4*N];
	void push(int l,int r,int i){
		if (tag[i].mx>0){
			tag[2*i].mx=max(tag[2*i].mx,tag[i].mx);
			tag[2*i+1].mx=max(tag[2*i+1].mx,tag[i].mx);
			seg[2*i].mx=max(seg[2*i].mx,tag[i].mx);
			seg[2*i+1].mx=max(seg[2*i+1].mx,tag[i].mx);
			tag[i].mx=0;
		}
		if (tag[i].mn<1e8){
			tag[2*i].mn=min(tag[2*i].mn,tag[i].mn);
			tag[2*i+1].mn=min(tag[2*i+1].mn,tag[i].mn);
			seg[2*i].mn=min(seg[2*i].mn,tag[i].mn);
			seg[2*i+1].mn=min(seg[2*i+1].mn,tag[i].mn);
			tag[i].mn=1e9;
		}
	}
	void modify(int l,int r,int i,int ll,int rr,int vmx,int vmn){
		if (ll>rr) return;
		if (ll<=l&&rr>=r){
			tag[i].mx=max(vmx,tag[i].mx);
			seg[i].mx=max(seg[i].mx,tag[i].mx);
			tag[i].mn=min(vmn,tag[i].mn);
			seg[i].mn=min(seg[i].mn,tag[i].mn);
			return;
		}
		int mid=(l+r)>>1;
		push(l,r,i);
		if (rr<=mid) modify(l,mid,2*i,ll,rr,vmx,vmn);
		else if (ll>mid) modify(mid+1,r,2*i+1,ll,rr,vmx,vmn);
		else {
			modify(l,mid,2*i,ll,mid,vmx,vmn);
			modify(mid+1,r,2*i+1,mid+1,rr,vmx,vmn);
		}
		seg[i].pull(seg[2*i],seg[2*i+1]);
	}
	Node query(int l,int r,int i,int ll,int rr){
		if (ll>rr){
			Node np; np.mn=1e9; np.mx=-1;
			return np;
		}
		if (ll<=l&&rr>=r) return seg[i];
		int mid=(l+r)>>1;
		push(l,r,i);
		if (rr<=mid) return query(l,mid,2*i,ll,rr);
		else if (ll>mid) return query(mid+1,r,2*i+1,ll,rr);
		else {
			Node np;
			np.pull(query(l,mid,2*i,ll,mid),query(mid+1,r,2*i+1,mid+1,rr));
			return np;
		}
	}
}seg[30];
int n,k,m;
signed main(){
	fast
	cin>>n>>k>>m;
	for (int j=0;j<30;j++){
		for (int i=0;i<4*n+5;i++){
			seg[j].seg[i].mx=-1;
			seg[j].seg[i].mn=1e9;
			seg[j].tag[i].mx=-1;
			seg[j].tag[i].mn=1e9; 
		}
	}

	for (int i=1;i<=m;i++){
		int a,b; cin>>a>>b;
		if (a<b){
			seg[0].modify(1,n,1,a,min(a+k-1,b),b,1e9);
		}
		else {
			seg[0].modify(1,n,1,max(b,a-k+1),a,-1,b);
		}
	}
	/*
	for (int i=1;i<=n;i++){
		Node np=seg[0].query(1,n,1,i,i);
		cout<<"{"<<np.mx<<","<<np.mn<<"} ";
	}
	cout<<'\n';
	*/
	for (int i=1;i<25;i++){
		for (int j=1;j<=n;j++){
			Node qu=seg[i-1].query(1,n,1,j,j);
			Node np=seg[i-1].query(1,n,1,min(qu.mn,j),max(qu.mx,j));
			seg[i].modify(1,n,1,j,j,np.mx,np.mn);
	//		cout<<"{"<<np.mx<<","<<np.mn<<"} ";
		}
	//	cout<<'\n';
	}
	int q; cin>>q;
	while (q--){
		int a,b,ans=0; cin>>a>>b;
		Node np; np.mn=a; np.mx=a;
		for (int i=23;i>=0;i--){
			Node tans=seg[i].query(1,n,1,np.mn,np.mx);
			if (a>b){
				if (tans.mn>b){
					ans+=(1LL<<i);
					np.pull(np,tans);
				}
			}
			else {
				if (tans.mx<b){
					ans+=(1LL<<i);
					np.pull(np,tans);
				}
			}
		}
		if (ans>5000000) cout<<-1<<'\n';
		else cout<<ans+1<<'\n';
	}
}

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