oj.uz

Submission #532485

# Submission time Handle Problem Language Result Execution time Memory
532485 2022-03-03T03:07:00 Z Haruto810198 Railway Trip 2 (JOI22_ho_t4) C++17
100 / 100
 876 ms 347872 KB 
#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
//const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 100010;

int n, k, m, q;

// ST[0].l, r
vi evmin[MAX], evmax[MAX];
multiset<int> Smin, Smax;

struct SparseTable{
	int l[MAX], r[MAX];
	int stl[MAX][20], str[MAX][20];
	
	// build stl, str
	void build(){
		FOR(i, 1, n, 1){
			stl[i][0] = l[i];
			str[i][0] = r[i];
		}

		FOR(j, 1, 19, 1){
			FOR(i, 1, n, 1){
				int ii = i + (1<<(j-1));
				if(ii <= n){
					stl[i][j] = min(stl[i][j-1], stl[ii][j-1]);
					str[i][j] = max(str[i][j-1], str[ii][j-1]);
				}
				else{
					stl[i][j] = stl[i][j-1];
					str[i][j] = str[i][j-1];
				}
			}
		}
	}
	
	// query range min, max
	inline pii query(int ql, int qr){
		int rk = __lg(qr - ql + 1);
		return mkp(min(stl[ql][rk], stl[qr - (1<<rk) + 1][rk]), max(str[ql][rk], str[qr - (1<<rk) + 1][rk]));
	}
};

SparseTable ST[20];

void transition(int j){
	FOR(i, 1, n, 1){
		int ql = ST[j-1].l[i];
		int qr = ST[j-1].r[i];
		pii ans = ST[j-1].query(ql, qr);
		ST[j].l[i] = ans.F;
		ST[j].r[i] = ans.S;
	}
}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>k;

	// build ST[0].l, ST[0].r
	cin>>m;
	FOR(i, 1, m, 1){
		int from, to;
		int l, r;

		cin>>from>>to;
		if(from > to){
			// [from - k + 1, from], min -> to
			l = max(from - k + 1, to);
			r = from;
			evmin[l].pb(to);
			evmin[r+1].pb(-to);
		}
		else{
			// [from, from + k - 1], max -> to
			l = from;
			r = min(from + k - 1, to);
			evmax[l].pb(to);
			evmax[r+1].pb(-to);
		}
	}
	
	FOR(i, 1, n, 1){
		ST[0].l[i] = ST[0].r[i] = i;
	}

	FOR(i, 1, n, 1){
		for(int e : evmin[i]){
			if(e > 0) Smin.insert(e);
			else Smin.erase(Smin.find(-e));
		}

		for(int e : evmax[i]){
			if(e > 0) Smax.insert(e);
			else Smax.erase(Smax.find(-e));
		}

		if(!Smin.empty()) ST[0].l[i] = min(ST[0].l[i], *Smin.begin());
		if(!Smax.empty()) ST[0].r[i] = max(ST[0].r[i], *prev(Smax.end()));
	}
	
	/*
	cerr<<"ST[0] : "<<endl;
	cerr<<"<- : ";
	FOR(i, 1, n, 1){
		cerr<<ST[0].l[i]<<" ";
	}
	cerr<<endl;
	cerr<<"-> : ";
	FOR(i, 1, n, 1){
		cerr<<ST[0].r[i]<<" ";
	}
	cerr<<endl;
	*/
	
	// build ST[0] ~ ST[19]
	ST[0].build();
	FOR(j, 1, 19, 1){
		transition(j);
		ST[j].build();
	}

	// query
	cin>>q;
	while(q--){
		int qs, qt;
		cin>>qs>>qt;
		
		int res = 0;
		int lp = qs, rp = qs;
		pii nxt;

		for(int j = 19; j >= 0; j--){
			nxt = ST[j].query(lp, rp);
			if(!(nxt.F <= qt and qt <= nxt.S)){
				lp = nxt.F;
				rp = nxt.S;
				res += (1<<j);
			}
		}
		
		nxt = ST[0].query(lp, rp);
		if(!(lp <= qt and qt <= rp)){
			lp = nxt.F;
			rp = nxt.S;
			res += 1;
		}

		if(res > 1e6) res = -1;
		cout<<res<<'\n';
	}
	
	return 0;

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 4 ms 6476 KB Output is correct
3 Correct 4 ms 6552 KB Output is correct
4 Correct 4 ms 6476 KB Output is correct
5 Correct 4 ms 6548 KB Output is correct
6 Correct 4 ms 6476 KB Output is correct
7 Correct 4 ms 6476 KB Output is correct
8 Correct 4 ms 6604 KB Output is correct
9 Correct 4 ms 6476 KB Output is correct
10 Correct 3 ms 5452 KB Output is correct
11 Correct 4 ms 6476 KB Output is correct
12 Correct 4 ms 6476 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 4 ms 6476 KB Output is correct
3 Correct 4 ms 6552 KB Output is correct
4 Correct 4 ms 6476 KB Output is correct
5 Correct 4 ms 6548 KB Output is correct
6 Correct 4 ms 6476 KB Output is correct
7 Correct 4 ms 6476 KB Output is correct
8 Correct 4 ms 6604 KB Output is correct
9 Correct 4 ms 6476 KB Output is correct
10 Correct 3 ms 5452 KB Output is correct
11 Correct 4 ms 6476 KB Output is correct
12 Correct 4 ms 6476 KB Output is correct
13 Correct 10 ms 12068 KB Output is correct
14 Correct 9 ms 12156 KB Output is correct
15 Correct 8 ms 12108 KB Output is correct
16 Correct 9 ms 12196 KB Output is correct
17 Correct 10 ms 12144 KB Output is correct
18 Correct 9 ms 12236 KB Output is correct
19 Correct 9 ms 11904 KB Output is correct
20 Correct 10 ms 12236 KB Output is correct
21 Correct 9 ms 12108 KB Output is correct
22 Correct 10 ms 12196 KB Output is correct
23 Correct 9 ms 12108 KB Output is correct
24 Correct 9 ms 12108 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 337560 KB Output is correct
2 Correct 642 ms 337540 KB Output is correct
3 Correct 638 ms 337852 KB Output is correct
4 Correct 619 ms 337544 KB Output is correct
5 Correct 770 ms 344044 KB Output is correct
6 Correct 690 ms 342288 KB Output is correct
7 Correct 676 ms 347444 KB Output is correct
8 Correct 628 ms 337908 KB Output is correct
9 Correct 671 ms 341144 KB Output is correct
10 Correct 670 ms 341508 KB Output is correct
11 Correct 690 ms 341808 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 343020 KB Output is correct
2 Correct 751 ms 344548 KB Output is correct
3 Correct 679 ms 341828 KB Output is correct
4 Correct 734 ms 347872 KB Output is correct
5 Correct 753 ms 343784 KB Output is correct
6 Correct 770 ms 346776 KB Output is correct
7 Correct 781 ms 340528 KB Output is correct
8 Correct 813 ms 339688 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 340424 KB Output is correct
2 Correct 754 ms 337312 KB Output is correct
3 Correct 709 ms 335692 KB Output is correct
4 Correct 713 ms 334684 KB Output is correct
5 Correct 654 ms 334572 KB Output is correct
6 Correct 625 ms 333944 KB Output is correct
7 Correct 637 ms 342076 KB Output is correct
8 Correct 4 ms 6476 KB Output is correct
9 Correct 9 ms 12192 KB Output is correct
10 Correct 759 ms 341392 KB Output is correct
11 Correct 790 ms 342900 KB Output is correct
12 Correct 746 ms 338412 KB Output is correct
13 Correct 752 ms 342824 KB Output is correct
14 Correct 4 ms 6476 KB Output is correct
15 Correct 10 ms 12060 KB Output is correct
16 Correct 656 ms 338088 KB Output is correct
17 Correct 756 ms 338200 KB Output is correct
18 Correct 768 ms 338244 KB Output is correct
19 Correct 714 ms 338372 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6528 KB Output is correct
2 Correct 4 ms 6476 KB Output is correct
3 Correct 4 ms 6552 KB Output is correct
4 Correct 4 ms 6476 KB Output is correct
5 Correct 4 ms 6548 KB Output is correct
6 Correct 4 ms 6476 KB Output is correct
7 Correct 4 ms 6476 KB Output is correct
8 Correct 4 ms 6604 KB Output is correct
9 Correct 4 ms 6476 KB Output is correct
10 Correct 3 ms 5452 KB Output is correct
11 Correct 4 ms 6476 KB Output is correct
12 Correct 4 ms 6476 KB Output is correct
13 Correct 10 ms 12068 KB Output is correct
14 Correct 9 ms 12156 KB Output is correct
15 Correct 8 ms 12108 KB Output is correct
16 Correct 9 ms 12196 KB Output is correct
17 Correct 10 ms 12144 KB Output is correct
18 Correct 9 ms 12236 KB Output is correct
19 Correct 9 ms 11904 KB Output is correct
20 Correct 10 ms 12236 KB Output is correct
21 Correct 9 ms 12108 KB Output is correct
22 Correct 10 ms 12196 KB Output is correct
23 Correct 9 ms 12108 KB Output is correct
24 Correct 9 ms 12108 KB Output is correct
25 Correct 649 ms 337560 KB Output is correct
26 Correct 642 ms 337540 KB Output is correct
27 Correct 638 ms 337852 KB Output is correct
28 Correct 619 ms 337544 KB Output is correct
29 Correct 770 ms 344044 KB Output is correct
30 Correct 690 ms 342288 KB Output is correct
31 Correct 676 ms 347444 KB Output is correct
32 Correct 628 ms 337908 KB Output is correct
33 Correct 671 ms 341144 KB Output is correct
34 Correct 670 ms 341508 KB Output is correct
35 Correct 690 ms 341808 KB Output is correct
36 Correct 719 ms 343020 KB Output is correct
37 Correct 751 ms 344548 KB Output is correct
38 Correct 679 ms 341828 KB Output is correct
39 Correct 734 ms 347872 KB Output is correct
40 Correct 753 ms 343784 KB Output is correct
41 Correct 770 ms 346776 KB Output is correct
42 Correct 781 ms 340528 KB Output is correct
43 Correct 813 ms 339688 KB Output is correct
44 Correct 876 ms 340424 KB Output is correct
45 Correct 754 ms 337312 KB Output is correct
46 Correct 709 ms 335692 KB Output is correct
47 Correct 713 ms 334684 KB Output is correct
48 Correct 654 ms 334572 KB Output is correct
49 Correct 625 ms 333944 KB Output is correct
50 Correct 637 ms 342076 KB Output is correct
51 Correct 4 ms 6476 KB Output is correct
52 Correct 9 ms 12192 KB Output is correct
53 Correct 759 ms 341392 KB Output is correct
54 Correct 790 ms 342900 KB Output is correct
55 Correct 746 ms 338412 KB Output is correct
56 Correct 752 ms 342824 KB Output is correct
57 Correct 4 ms 6476 KB Output is correct
58 Correct 10 ms 12060 KB Output is correct
59 Correct 656 ms 338088 KB Output is correct
60 Correct 756 ms 338200 KB Output is correct
61 Correct 768 ms 338244 KB Output is correct
62 Correct 714 ms 338372 KB Output is correct
63 Correct 726 ms 336792 KB Output is correct
64 Correct 756 ms 337104 KB Output is correct
65 Correct 758 ms 337052 KB Output is correct
66 Correct 785 ms 342336 KB Output is correct
67 Correct 738 ms 340252 KB Output is correct
68 Correct 742 ms 336736 KB Output is correct
69 Correct 759 ms 344144 KB Output is correct
70 Correct 748 ms 339692 KB Output is correct
71 Correct 783 ms 339604 KB Output is correct