Submission #935005

#	Time	Username	Problem	Language	Result	Execution time	Memory
935005		koukirocks	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	1605 ms	113716 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 build(int l,int r,int id) {
		;
	}
	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;
}

void build(int k,int l=1,int r=n,int id=1) {
	if (l==r) {
		int farlft=lft[k-1].query(l,l),farrt=rt[k-1].query(l,l);
		rt[k].tree[id]=rt[k-1].query(farlft,farrt);
		rt[k].lazy[id]=0;
		lft[k].tree[id]=lft[k-1].query(farlft,farrt);
		lft[k].lazy[id]=INF;
		return ;
	}
	int m=l+r>>1;
	build(k,l,m,id<<1);
	build(k,m+1,r,id<<1|1);
	rt[k].tree[id]=max(rt[k].tree[id<<1],rt[k].tree[id<<1|1]);
	rt[k].lazy[id]=0;
	lft[k].tree[id]=min(lft[k].tree[id<<1],lft[k].tree[id<<1|1]);
	lft[k].lazy[id]=INF;
}

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);
	}
	lft[0].init(1,n,1);
	rt[0].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 i=1;i<18;i++) {
		build(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:100:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |   int m=l+r>>1;
      |         ~^~
Main.cpp: In member function 'int SegTreeMax::query(int, int, int, int, int)':
Main.cpp:112:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |   int m=l+r>>1;
      |         ~^~
Main.cpp: In function 'void build(int, int, int, int)':
Main.cpp:141:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  141 |  int m=l+r>>1;
      |        ~^~

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