Submission #872020

#	Time	Username	Problem	Language	Result	Execution time	Memory
872020		Hyojin	버스 (JOI14_bus)	C++17	100 / 100	162 ms	24324 KiB

bus

#include <bits/stdc++.h>
using namespace std;
#define bit(n,i) ((n>>i)&1) 
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii> 
#define fi first
#define se second
#define ll long long
#define debug(x) cerr << #x << ' ' << x << '\n'
#define dbg(x) cerr<<#x<<' '<<x<<' '
const int base=31;
const int MOD=1e9+7;
const int N=3e5+5;
const int M=3e5+5;
const int inf=1e9;
int n,m,worst[N],mx[N];
array<int,5>a[M],b[M];
/*
	we can only go to school from bus that y==n 
	so find the worst time 
	just do some sweep 
*/
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#ifdef Shiho
    	freopen("izumi_shiho_supremacy.in","r", stdin);
    	freopen("izumi_shiho_supremacy.out","w", stdout);
	#endif
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		cin>>a[i][0]>>a[i][1]>>a[i][2]>>a[i][3];
		a[i][4]=i;
		b[i]=a[i];
	}
	sort(a+1,a+m+1,[&](array<int,5>x,array<int,5>y){
		return (x[2]<y[2])||(x[2]==y[2]&&x[3]<y[3]);
	});
	sort(b+1,b+m+1,[&](array<int,5>x,array<int,5>y){
		return (x[3]<y[3])||(x[3]==y[3]&&x[2]<y[2]);
	});
	fill(mx+1,mx+n+1,-inf);
	int j=1;
	for (int i=1;i<=m;i++)
	{
		auto [s,t,x,y,id]=a[i];
		if (s==1) 
		{
			worst[id]=x;
			continue;
		}
		while (j<=m&&b[j][3]<=x)
		{
			mx[b[j][1]]=max(mx[b[j][1]],worst[b[j][4]]);
			++j;
		}
		worst[id]=mx[s];
	}
	vector<pii>answer;
	int cur=-inf;
	answer.pb({-1,cur});
	for (int i=1;i<=m;i++)
	{
		if (b[i][1]==n)
		{
			cur=max(cur,worst[b[i][4]]);
			answer.pb({b[i][3],cur});
		}
	}
	int q;
	cin>>q;
	while (q--)
	{
		int x;
		cin>>x;
		int it=upper_bound(all(answer),make_pair(x,inf))-answer.begin()-1;
		cout<<(answer[it].se==-inf?-1:answer[it].se)<<"\n";
	}
	return 0;	
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 50 / 50