Submission #934997

#	Time	Username	Problem	Language	Result	Execution time	Memory
934997		koukirocks	Railway Trip 2 (JOI22_ho_t4)	C++17	52 / 100	2049 ms	117248 KiB

Main

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=1e5+10,P=998244353;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
 
int n,k,m;
vector<pii> trn[2];

struct SegTreeMin{
	int tree[MAX*4];
	int lazy[MAX*4];
	void init(int l,int r,int id) {
		if (l==r) {
			tree[id]=l;
			lazy[id]=INF;
			return;
		}
		int m=l+r>>1;
		init(l,m,id<<1);
		init(m+1,r,id<<1|1);
		tree[id]=min(tree[id<<1],tree[id<<1|1]);
		lazy[id]=INF;
	}
	void pd(int l,int r,int id) {
		if (lazy[id]!=INF) {
			lazy[id<<1]=min(lazy[id<<1],lazy[id]);
			lazy[id<<1|1]=min(lazy[id<<1|1],lazy[id]);
			tree[id<<1]=min(tree[id<<1],lazy[id]);
			tree[id<<1|1]=min(tree[id<<1|1],lazy[id]);
			lazy[id]=INF;
		}
	}
	void update(int val,int L,int R,int l=1,int r=n,int id=1) {
//		cout<<l<<" "<<r<<" "<<val<<" upd\n";
		if (L<=l and r<=R) {
			tree[id]=min(tree[id],val);
			lazy[id]=min(lazy[id],val);
			return;
		}
		int m=l+r>>1;
		pd(l,r,id);
		if (L<=m) update(val,L,R,l,m,id<<1);
		if (m<R) update(val,L,R,m+1,r,id<<1|1);
		tree[id]=min(tree[id<<1],tree[id<<1|1]);
	}
	int query(int L,int R,int l=1,int r=n,int id=1) {
	//	cout<<l<<" "<<r<<" "<<dir<<" "<<id<<" q\n";
		if (L<=l and r<=R) return tree[id];
		int m=l+r>>1;
		pd(l,r,id);
		int ans=INF;
		if (L<=m) ans=min(ans,query(L,R,l,m,id<<1));
		if (m<R) ans=min(ans,query(L,R,m+1,r,id<<1|1));
		return ans;
	}
};

struct SegTreeMax{
	int tree[MAX*4];
	int lazy[MAX*4];
	void init(int l,int r,int id) {
		if (l==r) {
			tree[id]=l;
			lazy[id]=0;
			return;
		}
		int m=l+r>>1;
		init(l,m,id<<1);
		init(m+1,r,id<<1|1);
		tree[id]=max(tree[id<<1],tree[id<<1|1]);
		lazy[id]=0;
	}
	void pd(int l,int r,int id) {
		if (lazy[id]!=0) {
			lazy[id<<1]=max(lazy[id<<1],lazy[id]);
			lazy[id<<1|1]=max(lazy[id<<1|1],lazy[id]);
			tree[id<<1]=max(tree[id<<1],lazy[id]);
			tree[id<<1|1]=max(tree[id<<1|1],lazy[id]);
			lazy[id]=0;
		}
	}
	void update(int val,int L,int R,int l=1,int r=n,int id=1) {
		if (L<=l and r<=R) {
			tree[id]=max(tree[id],val);
			lazy[id]=max(lazy[id],val);
			return;
		}
		int m=l+r>>1;
		pd(l,r,id);
		if (L<=m) update(val,L,R,l,m,id<<1);
		if (m<R) update(val,L,R,m+1,r,id<<1|1);
		tree[id]=max(tree[id<<1],tree[id<<1|1]);
	}
	int query(int L,int R,int l=1,int r=n,int id=1) {
//		cout<<l<<" "<<r<<" "<<id<<" q\n";
		if (L<=l and r<=R) {
//			cout<<l<<" "<<r<<" "<<tree[id]<<"\n";
			return tree[id];
		}
		int m=l+r>>1;
		pd(l,r,id);
		int ans=0;
		if (L<=m) ans=max(ans,query(L,R,l,m,id<<1));
		if (m<R) ans=max(ans,query(L,R,m+1,r,id<<1|1));
		return ans;
	}
};

SegTreeMin lft[18];
SegTreeMax rt[18];

bool extend(int &l,int &r,int t,int k) {
	int nl=lft[k].query(l,r),nr=rt[k].query(l,r);
//	cout<<nl<<" "<<nr<<" nl nr\n";
	if (nl<=t and t<=nr) return false;
	l=nl;r=nr;
	return true;
}

int main() {
	speed;
	cin>>n>>k;
	cin>>m;
	for (int i=0;i<m;i++) {
		int a,b;
		cin>>a>>b;
		trn[(a<b)].emplace_back(a,b);
	}
	for (int i=0;i<18;i++) {
		lft[i].init(1,n,1);
		rt[i].init(1,n,1);
	}
	for (pii i:trn[0]) {
		int s=i.first,t=i.second;
		lft[0].update(t,max(t,s-k+1),s);
//		cout<<max(t,s-k+1)<<" "<<s<<" "<<t<<" lft\n";
	}
//	for (int i=1;i<=n;i++) cout<<lft[0].query(i,i)<<" ";
//	cout<<"\n";
//	for (int i=1;i<=n;i++) cout<<rt[0].query(i,i)<<" ";
//	cout<<"\n";
	for (pii i:trn[1]) {
		int s=i.first,t=i.second;
		rt[0].update(t,s,min(t,s+k-1));
//		cout<<s<<" "<<min(t,s+k-1)<<" "<<t<<" rt\n";
	}
//	cout<<rt[0].query(3,5)<<" vvdfbgsdgbsgf\n";
	for (int k=1;k<18;k++) {
		for (int i=1;i<=n;i++) {
//			cout<<k<<" "<<i<<" ki\n";
			int farlft=lft[k-1].query(i,i),farrt=rt[k-1].query(i,i);
//			cout<<farlft<<" "<<farrt<<" lr\n";
//			cout<<lft[k-1].query(farlft,farrt)<<" "<<rt[k-1].query(farlft,farrt)<<" lr rslt\n";
			lft[k].update(lft[k-1].query(farlft,farrt),i,i);
			rt[k].update(rt[k-1].query(farlft,farrt),i,i);
		}
	}
//	for (int k=0;k<18;k++) {
//		for (int i=1;i<=n;i++) cout<<lft[k].query(i,i)<<" ";
//		cout<<"\n";
//		for (int i=1;i<=n;i++) cout<<rt[k].query(i,i)<<" ";
//		cout<<"\n\n";
//	}
	cout<<flush;
	int q;
	cin>>q;
	while (q--) {
		int s,t;
		cin>>s>>t;
		int l=s,r=s;
		ll ans=0;
		for (int k=18-1;k>=0;k--) {
			bool suc=extend(l,r,t,k);
			if (suc) ans+=(1<<k);
//			cout<<k<<" "<<suc<<" ksuc\n";
		}
		if (!extend(l,r,t,0)) cout<<ans+1<<"\n";
		else cout<<"-1\n";
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void SegTreeMin::init(int, int, int)':
Main.cpp:27:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   int m=l+r>>1;
      |         ~^~
Main.cpp: In member function 'void SegTreeMin::update(int, int, int, int, int, int)':
Main.cpp:49:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int m=l+r>>1;
      |         ~^~
Main.cpp: In member function 'int SegTreeMin::query(int, int, int, int, int)':
Main.cpp:58:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |   int m=l+r>>1;
      |         ~^~
Main.cpp: In member function 'void SegTreeMax::init(int, int, int)':
Main.cpp:76:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   int m=l+r>>1;
      |         ~^~
Main.cpp: In member function 'void SegTreeMax::update(int, int, int, int, int, int)':
Main.cpp:97:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |   int m=l+r>>1;
      |         ~^~
Main.cpp: In member function 'int SegTreeMax::query(int, int, int, int, int)':
Main.cpp:109:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |   int m=l+r>>1;
      |         ~^~

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