Submission #928310

#	Time	Username	Problem	Language	Result	Execution time	Memory
928310		pcc	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	487 ms	98372 KiB

Main

#include <bits/stdc++.h>
using namespace std;


#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 1e5+10;

int N,M,K,Q;
pii range[mxn];
pii dp[mxn][20];
vector<int> lop[mxn],rop[mxn];

struct SEG{
	pii segtree[mxn*4];
	SEG(){
		memset(segtree,0,sizeof(segtree));
	}
	void build(int now,int l,int r,int lvl){
		if(l == r){
			segtree[now] = dp[l][lvl];
			return;
		}
		int mid = (l+r)>>1;
		build(now*2+1,l,mid,lvl);
		build(now*2+2,mid+1,r,lvl);
		segtree[now].fs = min(segtree[now*2+1].fs,segtree[now*2+2].fs);
		segtree[now].sc = max(segtree[now*2+1].sc,segtree[now*2+2].sc);
	}
	pii getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return segtree[now];
		int mid = (l+r)>>1;
		if(mid>=e)return getval(now*2+1,l,mid,s,e);
		else if(mid<s)return getval(now*2+2,mid+1,r,s,e);
		else{
			auto ta = getval(now*2+1,l,mid,s,e),tb = getval(now*2+2,mid+1,r,s,e);
			return make_pair(min(ta.fs,tb.fs),max(ta.sc,tb.sc));
		}
	}
};

SEG seg[20];

void solve(){
	int s,e;
	cin>>s>>e;
	{
		pii big = dp[s][19];
		if(big.fs>e||big.sc<e){
			cout<<"-1\n";
			return;
		}
	}
	pii now = {s,s};
	int ans = 0;
	for(int i = 19;i>=0;i--){
		pii nxt = now;
		nxt = seg[i].getval(0,1,N,nxt.fs,nxt.sc);
		if(nxt.fs>e||nxt.sc<e){
			now = nxt;
			ans += 1<<i;
		}
	}
	if(now.fs>e||now.sc<e)ans++;
	cout<<ans<<'\n';
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>K>>M;
	for(int i = 0;i<M;i++){
		int a,b;
		cin>>a>>b;
		if(a<=b){
			int e = min(b+1,a+K);
			rop[a].push_back(b);
			rop[e].push_back(-b);
		}
		else{
			int e = max(b-1,a-K);
			lop[a].push_back(b);
			lop[e].push_back(-b);
		}
	}
	for(int i = 1;i<=N;i++)range[i].fs = range[i].sc = i;
	multiset<int> st;
	for(int i = 1;i<=N;i++){
		for(auto &j:rop[i]){
			if(j>0)st.insert(j);
			else st.erase(st.find(-j));
		}
		if(!st.empty())range[i].sc = *st.rbegin();
	}

	st.clear();
	for(int i = N;i>=1;i--){
		for(auto &j:lop[i]){
			if(j>0)st.insert(j);
			else st.erase(st.find(-j));
		}
		if(!st.empty())range[i].fs = *st.begin();
	}
	for(int i = 1;i<=N;i++)dp[i][0] = range[i];
	seg[0].build(0,1,N,0);
	for(int i = 1;i<20;i++){
		for(int j = 1;j<=N;j++){
			dp[j][i] = seg[i-1].getval(0,1,N,dp[j][i-1].fs,dp[j][i-1].sc);
		}
		seg[i].build(0,1,N,i);
	}
	/*
	for(int i = 0;i<20;i++){
		cout<<i<<":"<<endl;
		for(int j = 1;j<=N;j++)cout<<dp[j][i].fs<<' ';cout<<endl;
		//for(int j = 1;j<=N;j++)assert(dp[j][i].fs == seg[i].getval(0,1,N,j,j).fs);
		for(int j = 1;j<=N;j++)cout<<dp[j][i].sc<<' ';cout<<endl;
		for(int j = 1;j<=N;j++)cout<<seg[i].getval(0,1,N,j,j).fs<<' ';cout<<endl;
		for(int j = 1;j<=N;j++)cout<<seg[i].getval(0,1,N,j,j).sc<<' ';cout<<endl;
	}

   */
	cin>>Q;
	while(Q--)solve();
}

Compilation message (stderr)

Main.cpp: In constructor 'SEG::SEG()':
Main.cpp:18:35: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<int, int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   18 |   memset(segtree,0,sizeof(segtree));
      |                                   ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~

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