oj.uz

Submission #872015

# Submission time Handle Problem Language Result Execution time Memory
872015 2023-11-12T06:27:51 Z Hyojin 버스 (JOI14_bus) C++17
35 / 100
 157 ms 34808 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;
	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<<((it==-1||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 4564 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 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4580 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 2 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 6236 KB Output is correct
3 Correct 17 ms 6072 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 3 ms 4520 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 14 ms 4960 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 12 ms 5212 KB Output is correct
10 Correct 20 ms 6104 KB Output is correct
11 Correct 13 ms 5212 KB Output is correct
12 Correct 21 ms 6220 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 155 ms 34808 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 157 ms 34648 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -