Submission #675800

#	Time	Username	Problem	Language	Result	Execution time	Memory
675800		guagua0407	Railway Trip 2 (JOI22_ho_t4)	C++17	27 / 100	2077 ms	6836 KiB

Main

/*
燒雞
 燒雞
  燒雞    好想進選訓
 燒雞
燒雞
*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end() 
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

struct node{
	int mx=-1, mn=1e5+5;
	int stmx=-1,stmn=1e5+5;
};

const int mxn=1e5+5;
pair<int,int> jump[20][mxn];
int n,k,m;
node segtree[mxn*4];

void push(int v){
	segtree[v*2].mn=min(segtree[v*2].mn,segtree[v].stmn);
	segtree[v*2+1].mn=min(segtree[v*2+1].mn,segtree[v].stmn);
	segtree[v*2].mx=max(segtree[v*2].mx,segtree[v].stmx);
	segtree[v*2+1].mx=max(segtree[v*2+1].mx,segtree[v].stmx);
	segtree[v*2].stmn=min(segtree[v*2].stmn,segtree[v].stmn);
	segtree[v*2+1].stmn=min(segtree[v*2+1].stmn,segtree[v].stmn);
	segtree[v*2].stmx=max(segtree[v*2].stmx,segtree[v].stmx);
	segtree[v*2+1].stmx=max(segtree[v*2+1].stmx,segtree[v].stmx);
	segtree[v].stmn=1e5+5;
	segtree[v].stmx=-1;
}

void init(int l=1,int r=n,int v=1){
	segtree[v].mn=l,segtree[v].mx=r;
	if(l==r){
		return;
	}
	int mid=(l+r)/2;
	init(l,mid,v*2);
	init(mid+1,r,v*2+1);
}

void update1(int tl,int tr,int val,int l=1,int r=n,int v=1){
	if(tl>tr){
		return;
	}
	if(tl<=l and r<=tr){
		segtree[v].stmx=max(segtree[v].stmx,val);
		segtree[v].mx=max(segtree[v].mx,val);
		return;
	}
	push(v);
	int mid=(l+r)/2;
	update1(tl,min(mid,tr),val,l,mid,v*2);
	update1(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
	segtree[v].mx=max(segtree[v*2].mx,segtree[v*2+1].mx);
	segtree[v].mn=min(segtree[v*2].mn,segtree[v*2+1].mn);
}

void update2(int tl,int tr,int val,int l=1,int r=n,int v=1){
	if(tl>tr){
		return;
	}
	if(tl<=l and r<=tr){
		segtree[v].stmn=min(segtree[v].stmn,val);
		segtree[v].mn=min(segtree[v].mn,val);
		return;
	}
	push(v);
	int mid=(l+r)/2;
	update2(tl,min(mid,tr),val,l,mid,v*2);
	update2(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
	segtree[v].mn=min(segtree[v*2].mn,segtree[v*2+1].mn);
	segtree[v].mx=max(segtree[v*2].mx,segtree[v*2+1].mx);
}

pair<int,int> query(int tl,int tr,int l=1,int r=n,int v=1){
	if(tl>tr){
		return {n+1,-1};
	}
	if(tl<=l and r<=tr){
		return {segtree[v].mn,segtree[v].mx};
	}
	push(v);
	int mid=(l+r)/2;
	pair<int,int> x=query(tl,min(mid,tr),l,mid,v*2);
	pair<int,int> y=query(max(mid+1,tl),tr,mid+1,r,v*2+1);
	return {min(x.f,y.f),max(x.s,y.s)};
}

int main() {_
    //setIO("wayne");
	cin>>n>>k;
	cin>>m;
	init();
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		if(a<b){
			int tmp=min(a+k-1,b);
			update1(a,tmp,b);
		}
		else{
			int tmp=max(a-k+1,b);
			update2(tmp,a,b);
		}
	}
	int q;
	cin>>q;
	for(int i=0;i<q;i++){
		int a,b;
		cin>>a>>b;
		int l=a,r=a;
		int ans=0;
		while(b<l or b>r){
			//cout<<l<<' '<<r<<'\n';
			pair<int,int> tmp=query(l,r);
			l=tmp.f,r=tmp.s;
			ans++;
			if(ans>n){
				cout<<-1<<'\n';
				break;
			}
		}
		if(ans<=n) cout<<ans<<'\n';
	}
    return 0;
}
//maybe its multiset not set

Compilation message (stderr)

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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