oj.uz

Submission #872017

# Submission time Handle Problem Language Result Execution time Memory
872017 2023-11-12T06:30:07 Z Hyojin 버스 (JOI14_bus) C++17
35 / 100
 155 ms 25720 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=1e5+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 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4456 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 4444 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 5164 KB Output is correct
3 Correct 17 ms 5212 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4596 KB Output is correct
7 Correct 14 ms 4700 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 12 ms 4788 KB Output is correct
10 Correct 19 ms 5264 KB Output is correct
11 Correct 13 ms 4696 KB Output is correct
12 Correct 21 ms 5460 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 25720 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 155 ms 25716 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -