Submission #705896

#	Time	Username	Problem	Language	Result	Execution time	Memory
705896		safaricola	Railway Trip 2 (JOI22_ho_t4)	C++17	11 / 100	2077 ms	340944 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
#define rep(i,n) for (int i = 1; i <= n; i++) 
#define f first
#define s second
#define pb push_back
#define debug(x) cout<<#x<<" is "<<x<<endl;
const int N=100010;// log is ~17
int n,m,k,A,B,t[20][N][2],q;
struct node{
	int s,e,m,v,lazy;
	node *l, *r;
	node(int S, int E){
		s=S,e=E,m=(s+e)/2;
		v=1e9;lazy=1e9;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void prop(){
		if(lazy==1e9)return;
		v=min(lazy, v);
		if(s!=e){
			l->lazy= min(l->lazy, v);
			r->lazy= min(r->lazy, v);
		}
		lazy=1e9;
	}
	void upd(int S, int E, int V){
		if(s==S &&e==E) lazy= V;
		else{
			if(E<=m)l->upd(S,E,V);
			else if(S>m) r->upd(S,E,V);
			else{
				l-> upd(S,m,V);
				r->upd(m+1,E,V);
			}
			l-> prop();
			r->prop();
			v=min(l->v, r->v);
		}
	}
	int rmin(int S, int E){
		prop();
		if(s==S&&e==E){
			return v;
		}
		if(E<=m)return l->rmin(S,E);
		if(S>m) return r->rmin(S,E);
		return min(l-> rmin(S,m), r->rmin(m+1,E));
	}
}*lroot[20];// stores minpos you can go from i using 1 train
struct nodee{
	int s,e,m,v,lazy;
	nodee *l, *r;
	nodee(int S, int E){
		s=S,e=E,m=(s+e)/2;
		v=0;lazy=0;
		if(s!=e){
			l = new nodee(s,m);
			r=new nodee(m+1,e);
		}
	}
	void prop(){
		if(lazy==0)return;
		//debug (lazy) debug(v) debug(s) debug(e);
		if(s!=e){
			l->lazy= max(l->lazy, lazy);
			r->lazy= max(r->lazy, lazy);
		}
		v=max(lazy, v);
		lazy=0;
	}
	void upd(int S, int E, int V){
		if(s==S &&e==E) lazy= V;
		else{
			if(E<=m)l->upd(S,E,V);
			else if(S>m) r->upd(S,E,V);
			else{
				l-> upd(S,m,V);
				r->upd(m+1,E,V);
			}
			l-> prop();
			r->prop();
			v=max(l->v, r->v);
		}
	}
	int rmax(int S, int E){
		prop();
		//cout<<s<<' '<<e<<' '<<v<<endl;
		if(s==S&&e==E){
			return v;
		}
		if(E<=m)return l->rmax(S,E);	
		if(S>m) return r->rmax(S,E);
		return max(l-> rmax(S,m), r->rmax(m+1,E));
	}
}*rroot[20];// stores maxpos you can go from i using 1 train
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin>>n>>k>>m;
	rep(j,18){
		lroot[j-1]=new node(1,n+1);
		rroot[j-1]=new nodee(1,n+1);
		rep(i,n)lroot[j-1]->upd(i,i,i); //0 trains
		rep(i,n)rroot[j-1]->upd(i,i,i);
	}
	//store value for 1 train
	rep(i,m){
		cin>>A>>B;
		if(A>B){
			//right to left, min
			lroot[0]->upd(max(1,A-k+1),A,B);
		}else{
			// left to right, max
			rroot[0]->upd(A,min(n, A+k-1), B);
			//hopefully rroot is correct
		}
	}
	//rep(i,n)cout<<lroot[0]->rmin(i,i)<<' ';cout<<endl;
	//rep(i,n)cout<<rroot[0]->rmax(i,i)<<' ';cout<<endl;
	rep(j,17){
		rep(i,n){
			int leftt=lroot[j-1]->rmin(i,i), rightt=rroot[j-1]->rmax(i,i);
			lroot[j]->upd(i,i,lroot[j-1]->rmin(leftt,rightt));
			rroot[j]->upd(i,i,rroot[j-1]->rmax(leftt,rightt));
		}
		//rep(i,n)cout<<lroot[0]->rmin(i,i)<<' ';cout<<endl;
		//rep(i,n)cout<<rroot[0]->rmax(i,i)<<' ';cout<<endl;
	}
	
	cin>>q;
	rep(loopp,q){
		cin>>A>>B;
		int ans=0, leftt=A, rightt=A, lef, rig;
		//cout<<t[0][A][1]<<endl;
		for(int i=17; i>=0; i--){
			lef=lroot[i]->rmin(leftt, rightt);
			rig=rroot[i]->rmax(leftt, rightt);
			if (!(lef <= B && B <= rig)){
                ans += (1<<i);
				leftt=lef; rightt=rig;
            }
		}
		lef=lroot[0]->rmin(leftt, rightt);
		rig=rroot[0]->rmax(leftt, rightt);
		if(lef <= B && B <= rig)cout<<ans+1<<'\n';
		else cout<<-1<<'\n';
	}
}

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