oj.uz

Submission #531968

# Submission time Handle Problem Language Result Execution time Memory
531968 2022-03-02T02:04:00 Z yungyao Railway Trip 2 (JOI22_ho_t4) C++17
100 / 100
 477 ms 52280 KB 
/*


weak        weak  we      ak   we  akwea        weak  we
  weak    weak    we      ak   weak    weak    we  ak we
    weakweak      we      ak   wea       ak   we    akwe
      wea         we      ak   we        ak   we    akwe
      wea         we      ak   we        ak   we    akwe
      wea          eak  weak   we        ak    we  ak we
      wea            wea  ak   we        ak     weak  we
                                                      we
we      ak     wea  ak       weak                     we
 we    ak    wea  weak     wea  eak                   we
  we  ak    we      ak   wea      wea         we      we
   weak     we      ak   we        we         we      we
    we      we      ak   we        we         we      we
   we        wea  weak    wea    wea          weak  weak
weak           wea  akw      weak                weak


*/
//#define _GLIBCXX_DEBUG //is only used when couldn't find bug
using namespace std;
#pragma GCC optimize ("Ofast")
//headers
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <utility>
#include <bitset>
#include <set>
#include <string>
#include <stack>
#include <iomanip>
#include <map>
#include <memory.h>
#include <deque>
#include <time.h>
#include <assert.h>
#include <unordered_map>
#include <unordered_set>
#include <sstream>

//defines
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<LL>> vvl;
#define pb push_back
#define F first
#define S second
#define mid (LB+RB)/2
#define mkp make_pair

//iterators
#define iter(x) x.begin(),x.end()
#define aiter(a,n) a,a+n

//loops
#define REP(n) for (int ___=n > 0 ? n : 0;___--;)
#define REP0(i,n) for (int i=0,___=n;i<___;++i)
#define REP1(i,n) for (int i=1,___=n;i<=___;++i)
#define MEM(e,val) memset (e,val,sizeof(e))

/*
When he said Super Idol??摰寥瘝∩????急?甇????瘝∩??€?潛??105 簞C??皛湔輕皜滲?擐偌雿??乩????舐頝€?隡蝚???韏瑚?隞?賭?頧餉?憭梯揖撖寞╪?喟??抒?銝€?港??暹敺?敹?敶?撖寞?霂港?????曄?霈拇??亙??Ｚ蕭?芸楛?╪?喲???芋??
I really felt that.


every one is so dian except me
still too weak ?拙?
*/

//IO
#include <cstdio>
#include <iostream>
#include <fstream>
#define want_to_be_more_dian ios_base::sync_with_stdio(false),cin.tie(0);

//pbds
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
//tree <pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>;
*/

//constants
#include <climits>
const int maxn = 1e5+10,mod = 0;
const long long inf = 0;
const double eps = 0;

//workspace

struct segmenttree{
	pii val[maxn*4], arr[maxn];
	pii pull(pii l, pii r){
		return mkp(min(l.F, r.F), max(l.S, r.S));
	}
	void maketree(int cur, int LB, int RB){
		if (LB == RB) val[cur] = arr[LB];
		else{
			int m = (LB + RB) / 2;
			maketree(cur*2, LB, m);
			maketree(cur*2+1, m+1, RB);
			val[cur] = pull(val[cur*2], val[cur*2+1]);
		}
	}

	pii query(int l, int r, int cur, int LB, int RB){
		if (l == LB and r == RB) return val[cur];
		int m = (LB + RB) / 2;
		if (r <= m) return query(l, r, cur*2, LB, m);
		else if (l > m) return query(l, r, cur*2+1, m+1, RB);
		else return pull(query(l, m, cur*2, LB, m), query(m+1, r, cur*2+1, m+1, RB));
	}
}seg[17];

int mx[maxn], mn[maxn];

inline void solve(){
	int n, k, m, q;

	cin >> n >> k >> m;
	REP1(i, n) mx[i] = mn[i] = i;
	REP(m){
		int a, b;

		cin >> a >> b;
		mx[a] = max(mx[a], b);
		mn[a] = min(mn[a], b);
	}
	deque <pii> dq;
	REP1(i, n){
		while (!dq.empty() and mx[i] > dq.back().F) dq.pop_back();
		dq.pb(mkp(mx[i], i));
		if (dq.front().S + k <= i) dq.pop_front();
		mx[i] = dq.front().F;
	}
	while (!dq.empty()) dq.pop_back();
	for (int i=n;i;--i){
		while (!dq.empty() and mn[i] < dq.back().F) dq.pop_back();
		dq.pb(mkp(mn[i], i));
		if (dq.front().S - k >= i) dq.pop_front();
		mn[i] = dq.front().F;
	}
	REP1(i, n) seg[0].arr[i] = mkp(mn[i], mx[i]);
	seg[0].maketree(1, 1, n);
	REP1(i, 16){
		REP1(j, n) seg[i].arr[j] = seg[i-1].query(seg[i-1].arr[j].F, seg[i-1].arr[j].S, 1, 1, n);
		seg[i].maketree(1, 1, n);
	}
	cin >> q;
	REP(q){
		int b, ans = 0;
		pii a;

		cin >> a.F >> b; a.S = a.F;
		for (int i=16;i>=0;--i){
			pii s = seg[i].query(a.F, a.S, 1, 1, n);
			if (b < s.F or b > s.S){
				a = s;
				ans |= 1 << i;
			}
		}
		a = seg[0].query(a.F, a.S, 1, 1, n);
		if (b >= a.F and b <= a.S) cout << ans + 1 << '\n';
		else cout << "-1\n";
	}
}

signed main(){
	want_to_be_more_dian
	//int t,i=1; for (int ;cin;)//use in multi-testcases and end in EOF problems
	//int t,i=1; for (cin >> t;i<=t;++i)//use in multi-testcases problems
	//cout << "Case #" << i << ": ",//use in Google, FB competitions
	solve();//always used
	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 704 KB Output is correct
4 Correct 1 ms 708 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 708 KB Output is correct
13 Correct 6 ms 1360 KB Output is correct
14 Correct 5 ms 1348 KB Output is correct
15 Correct 3 ms 1356 KB Output is correct
16 Correct 3 ms 1356 KB Output is correct
17 Correct 6 ms 1352 KB Output is correct
18 Correct 2 ms 1356 KB Output is correct
19 Correct 6 ms 1356 KB Output is correct
20 Correct 3 ms 1416 KB Output is correct
21 Correct 2 ms 1392 KB Output is correct
22 Correct 4 ms 1356 KB Output is correct
23 Correct 5 ms 1356 KB Output is correct
24 Correct 5 ms 1356 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 50300 KB Output is correct
2 Correct 211 ms 50252 KB Output is correct
3 Correct 239 ms 50500 KB Output is correct
4 Correct 193 ms 50108 KB Output is correct
5 Correct 70 ms 51524 KB Output is correct
6 Correct 200 ms 51540 KB Output is correct
7 Correct 62 ms 52072 KB Output is correct
8 Correct 53 ms 50420 KB Output is correct
9 Correct 51 ms 50372 KB Output is correct
10 Correct 174 ms 51484 KB Output is correct
11 Correct 163 ms 51816 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 51140 KB Output is correct
2 Correct 247 ms 52280 KB Output is correct
3 Correct 380 ms 51124 KB Output is correct
4 Correct 125 ms 51528 KB Output is correct
5 Correct 129 ms 49804 KB Output is correct
6 Correct 124 ms 49608 KB Output is correct
7 Correct 275 ms 49628 KB Output is correct
8 Correct 281 ms 49752 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 49456 KB Output is correct
2 Correct 449 ms 49912 KB Output is correct
3 Correct 421 ms 49628 KB Output is correct
4 Correct 390 ms 49768 KB Output is correct
5 Correct 319 ms 49892 KB Output is correct
6 Correct 308 ms 49500 KB Output is correct
7 Correct 200 ms 50244 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 4 ms 1356 KB Output is correct
10 Correct 154 ms 49576 KB Output is correct
11 Correct 202 ms 49520 KB Output is correct
12 Correct 206 ms 49600 KB Output is correct
13 Correct 213 ms 49692 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 6 ms 1356 KB Output is correct
16 Correct 199 ms 49444 KB Output is correct
17 Correct 405 ms 49720 KB Output is correct
18 Correct 369 ms 49644 KB Output is correct
19 Correct 338 ms 49844 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 704 KB Output is correct
4 Correct 1 ms 708 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 708 KB Output is correct
13 Correct 6 ms 1360 KB Output is correct
14 Correct 5 ms 1348 KB Output is correct
15 Correct 3 ms 1356 KB Output is correct
16 Correct 3 ms 1356 KB Output is correct
17 Correct 6 ms 1352 KB Output is correct
18 Correct 2 ms 1356 KB Output is correct
19 Correct 6 ms 1356 KB Output is correct
20 Correct 3 ms 1416 KB Output is correct
21 Correct 2 ms 1392 KB Output is correct
22 Correct 4 ms 1356 KB Output is correct
23 Correct 5 ms 1356 KB Output is correct
24 Correct 5 ms 1356 KB Output is correct
25 Correct 221 ms 50300 KB Output is correct
26 Correct 211 ms 50252 KB Output is correct
27 Correct 239 ms 50500 KB Output is correct
28 Correct 193 ms 50108 KB Output is correct
29 Correct 70 ms 51524 KB Output is correct
30 Correct 200 ms 51540 KB Output is correct
31 Correct 62 ms 52072 KB Output is correct
32 Correct 53 ms 50420 KB Output is correct
33 Correct 51 ms 50372 KB Output is correct
34 Correct 174 ms 51484 KB Output is correct
35 Correct 163 ms 51816 KB Output is correct
36 Correct 270 ms 51140 KB Output is correct
37 Correct 247 ms 52280 KB Output is correct
38 Correct 380 ms 51124 KB Output is correct
39 Correct 125 ms 51528 KB Output is correct
40 Correct 129 ms 49804 KB Output is correct
41 Correct 124 ms 49608 KB Output is correct
42 Correct 275 ms 49628 KB Output is correct
43 Correct 281 ms 49752 KB Output is correct
44 Correct 288 ms 49456 KB Output is correct
45 Correct 449 ms 49912 KB Output is correct
46 Correct 421 ms 49628 KB Output is correct
47 Correct 390 ms 49768 KB Output is correct
48 Correct 319 ms 49892 KB Output is correct
49 Correct 308 ms 49500 KB Output is correct
50 Correct 200 ms 50244 KB Output is correct
51 Correct 1 ms 716 KB Output is correct
52 Correct 4 ms 1356 KB Output is correct
53 Correct 154 ms 49576 KB Output is correct
54 Correct 202 ms 49520 KB Output is correct
55 Correct 206 ms 49600 KB Output is correct
56 Correct 213 ms 49692 KB Output is correct
57 Correct 1 ms 716 KB Output is correct
58 Correct 6 ms 1356 KB Output is correct
59 Correct 199 ms 49444 KB Output is correct
60 Correct 405 ms 49720 KB Output is correct
61 Correct 369 ms 49644 KB Output is correct
62 Correct 338 ms 49844 KB Output is correct
63 Correct 379 ms 49644 KB Output is correct
64 Correct 477 ms 49668 KB Output is correct
65 Correct 401 ms 49856 KB Output is correct
66 Correct 94 ms 49936 KB Output is correct
67 Correct 363 ms 49668 KB Output is correct
68 Correct 292 ms 49428 KB Output is correct
69 Correct 116 ms 49496 KB Output is correct
70 Correct 339 ms 49524 KB Output is correct
71 Correct 370 ms 49600 KB Output is correct