oj.uz

Submission #872020

# Submission time Handle Problem Language Result Execution time Memory
872020 2023-11-12T06:31:59 Z Hyojin 버스 (JOI14_bus) C++17
100 / 100
 162 ms 24324 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4600 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 17 ms 5272 KB Output is correct
3 Correct 17 ms 5212 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 3 ms 4444 KB Output is correct
6 Correct 2 ms 4440 KB Output is correct
7 Correct 14 ms 4696 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 12 ms 4700 KB Output is correct
10 Correct 20 ms 5208 KB Output is correct
11 Correct 13 ms 4700 KB Output is correct
12 Correct 23 ms 5456 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 13908 KB Output is correct
2 Correct 143 ms 22612 KB Output is correct
3 Correct 142 ms 22612 KB Output is correct
4 Correct 144 ms 22784 KB Output is correct
5 Correct 141 ms 22612 KB Output is correct
6 Correct 141 ms 22764 KB Output is correct
7 Correct 145 ms 22100 KB Output is correct
8 Correct 142 ms 23116 KB Output is correct
9 Correct 140 ms 22612 KB Output is correct
10 Correct 136 ms 21332 KB Output is correct
11 Correct 137 ms 21620 KB Output is correct
12 Correct 136 ms 21376 KB Output is correct
13 Correct 137 ms 21384 KB Output is correct
14 Correct 137 ms 21376 KB Output is correct
15 Correct 135 ms 21336 KB Output is correct
16 Correct 40 ms 11488 KB Output is correct
17 Correct 40 ms 11488 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 15232 KB Output is correct
2 Correct 158 ms 23796 KB Output is correct
3 Correct 158 ms 24320 KB Output is correct
4 Correct 159 ms 24320 KB Output is correct
5 Correct 159 ms 23892 KB Output is correct
6 Correct 160 ms 24148 KB Output is correct
7 Correct 159 ms 23788 KB Output is correct
8 Correct 162 ms 24324 KB Output is correct
9 Correct 160 ms 24180 KB Output is correct
10 Correct 153 ms 23160 KB Output is correct
11 Correct 156 ms 23196 KB Output is correct
12 Correct 154 ms 23024 KB Output is correct
13 Correct 158 ms 23284 KB Output is correct
14 Correct 159 ms 23124 KB Output is correct
15 Correct 156 ms 23124 KB Output is correct
16 Correct 54 ms 12372 KB Output is correct