oj.uz

Submission #527591

# Submission time Handle Problem Language Result Execution time Memory
527591 2022-02-17T17:41:07 Z CSQ31 Railway Trip 2 (JOI22_ho_t4) C++17
27 / 100
 2000 ms 17488 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
const int MAXN = 1e5+2;
int l[17][MAXN],r[17][MAXN];
vector<int>e[MAXN],f[MAXN];
int main()
{
	owo
	int n,k,m,q;
	cin>>n>>k>>m;
	for(int i=0;i<m;i++){
		int s,t;
		cin>>s>>t;
		if(s < t){
			e[s].pb(t);
			e[min(s+k,t+1)].pb(-t);
		}else{
			f[s].pb(t);
			f[max(s-k,t-1)].pb(-t);
		}
	}
	multiset<int,greater<int>>ss;
	for(int i=1;i<=n;i++){
		for(int x:e[i]){
			if(x>0)ss.insert(x);
			else ss.erase(ss.find(-x));
		}
		if(ss.empty())r[0][i] = i;
		else r[0][i] = *ss.begin();
	}
	ss.clear();
	for(int i=n;i>=1;i--){
		for(int x:f[i]){
			if(x>0)ss.insert(-x);
			else ss.erase(ss.find(x));
		}
		if(ss.empty())l[0][i] = i;
		else l[0][i] = -(*ss.begin());
	}
	cin>>q;
	while(q--){
		int s,t;
		cin>>s>>t;
		int L=s,R=s;
		int ans = 0;
		while(t<L || t>R){
			int mnl = L;
			int mxr = R;
			for(int i=L;i<=R;i++){
				mnl = min(mnl,l[0][i]);
				mxr = max(mxr,r[0][i]);
			}
			if(mnl == L && mxr == R){
				ans = -1;
				break;
			}
			L = mnl;
			R = mxr;
			ans++;
		}
		cout<<ans<<'\n';
	}

	
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB Output is correct
2 Correct 11 ms 5036 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB Output is correct
2 Correct 11 ms 5036 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 1614 ms 5092 KB Output is correct
14 Correct 946 ms 5208 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 8 ms 5112 KB Output is correct
17 Correct 214 ms 5152 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Correct 4 ms 5068 KB Output is correct
20 Correct 5 ms 5068 KB Output is correct
21 Correct 3 ms 5068 KB Output is correct
22 Correct 4 ms 5148 KB Output is correct
23 Correct 17 ms 5068 KB Output is correct
24 Correct 8 ms 5068 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1608 ms 8608 KB Output is correct
2 Correct 718 ms 8704 KB Output is correct
3 Correct 1996 ms 8884 KB Output is correct
4 Correct 137 ms 8764 KB Output is correct
5 Correct 166 ms 12552 KB Output is correct
6 Correct 116 ms 11980 KB Output is correct
7 Correct 113 ms 17488 KB Output is correct
8 Correct 72 ms 10740 KB Output is correct
9 Correct 79 ms 10848 KB Output is correct
10 Correct 129 ms 11372 KB Output is correct
11 Correct 143 ms 11348 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 11844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 12488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB Output is correct
2 Correct 11 ms 5036 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 1614 ms 5092 KB Output is correct
14 Correct 946 ms 5208 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 8 ms 5112 KB Output is correct
17 Correct 214 ms 5152 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Correct 4 ms 5068 KB Output is correct
20 Correct 5 ms 5068 KB Output is correct
21 Correct 3 ms 5068 KB Output is correct
22 Correct 4 ms 5148 KB Output is correct
23 Correct 17 ms 5068 KB Output is correct
24 Correct 8 ms 5068 KB Output is correct
25 Correct 1608 ms 8608 KB Output is correct
26 Correct 718 ms 8704 KB Output is correct
27 Correct 1996 ms 8884 KB Output is correct
28 Correct 137 ms 8764 KB Output is correct
29 Correct 166 ms 12552 KB Output is correct
30 Correct 116 ms 11980 KB Output is correct
31 Correct 113 ms 17488 KB Output is correct
32 Correct 72 ms 10740 KB Output is correct
33 Correct 79 ms 10848 KB Output is correct
34 Correct 129 ms 11372 KB Output is correct
35 Correct 143 ms 11348 KB Output is correct
36 Execution timed out 2077 ms 11844 KB Time limit exceeded
37 Halted 0 ms 0 KB -