oj.uz

Submission #795843

# Submission time Handle Problem Language Result Execution time Memory
795843 2023-07-27T17:29:51 Z denniskim Railway Trip 2 (JOI22_ho_t4) C++17
54 / 100
 863 ms 104044 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll n, K;
ll m;
ll q;
pll a[200010];
ll L, R;
pll b[200010];
ll Lspa[200010][21];
ll Rspa[200010][21];

struct segtree
{
	pll seg[1000010][2];
	pll lazy[1000010][2];
	
	void init(ll no, ll s, ll e)
	{
		lazy[no][0] = {-INF, 0};
		lazy[no][1] = {INF, 0};
		seg[no][0] = {-INF, 0};
		seg[no][1] = {INF, 0};

		if(s == e)
			return;
		
		init(no << 1, s, (s + e) >> 1);
		init(no << 1 | 1, ((s + e) >> 1) + 1, e);
	}
	
	void prop(ll no, ll s, ll e)
	{
		if(seg[no][0].fi < lazy[no][0].fi)
			seg[no][0] = lazy[no][0];
		
		if(s != e)
		{
			if(lazy[no << 1][0].fi < lazy[no][0].fi)
				lazy[no << 1][0] = lazy[no][0];
			
			if(lazy[no << 1 | 1][0].fi < lazy[no][0].fi)
				lazy[no << 1 | 1][0] = lazy[no][0];
		}
		
		lazy[no][0] = {-INF, 0};

		if(seg[no][1].fi > lazy[no][1].fi)
			seg[no][1] = lazy[no][1];
		
		if(s != e)
		{
			if(lazy[no << 1][1].fi > lazy[no][1].fi)
				lazy[no << 1][1] = lazy[no][1];
			
			if(lazy[no << 1 | 1][1].fi > lazy[no][1].fi)
				lazy[no << 1 | 1][1] = lazy[no][1];
		}
		
		lazy[no][1] = {INF, 0};
	}
	
	void update(ll no, ll s, ll e, ll l, ll r, ll v1, ll v2)
	{
		prop(no, s, e);
		
		if(e < l || r < s)
			return;
		
		if(l <= s && e <= r)
		{
			if(seg[no][0].fi < v1)
				seg[no][0] = {v1, v2};

			if(seg[no][1].fi > v1)
				seg[no][1] = {v1, v2};

			if(s != e)
			{
				if(lazy[no << 1][0].fi < v1)
					lazy[no << 1][0] = {v1, v2};

				if(lazy[no << 1][1].fi > v1)
					lazy[no << 1][1] = {v1, v2};
				
				if(lazy[no << 1 | 1][0].fi < v1)
					lazy[no << 1 | 1][0] = {v1, v2};

				if(lazy[no << 1 | 1][1].fi > v1)
					lazy[no << 1 | 1][1] = {v1, v2};
			}

			return;
		}
		
		update(no << 1, s, (s + e) >> 1, l, r, v1, v2);
		update(no << 1 | 1, ((s + e) >> 1) + 1, e, l, r, v1, v2);
		
		if(seg[no << 1][0].fi < seg[no << 1 | 1][0].fi)
			seg[no][0] = seg[no << 1 | 1][0];
		else
			seg[no][0] = seg[no << 1][0];
		
		if(seg[no << 1][1].fi > seg[no << 1 | 1][1].fi)
			seg[no][1] = seg[no << 1 | 1][1];
		else
			seg[no][1] = seg[no << 1][1];
	}
	
	pair<pll, pll> query(ll no, ll s, ll e, ll l, ll r)
	{
		prop(no, s, e);
		
		if(e < l || r < s)
			return {{-INF, 0}, {INF, 0}};
		
		if(l <= s && e <= r)
			return {seg[no][0], seg[no][1]};
		
		pair<pll, pll> LL = query(no << 1, s, (s + e) >> 1, l, r);
		pair<pll, pll> RR = query(no << 1 | 1, ((s + e) >> 1) + 1, e, l, r);
		pair<pll, pll> ret;
		
		if(LL.fi.fi > RR.fi.fi)
			ret.fi = LL.fi;
		else
			ret.fi = RR.fi;
		
		if(LL.se.fi < RR.se.fi)
			ret.se = LL.se;
		else
			ret.se = RR.se;

		return ret;
	}
}segt, segt2;

void RR(void)
{
	ll cc = 0;
	
	for(ll i = 1 ; i <= m ; i++)
	{
		if(a[i].fi < a[i].se)
			b[cc++] = {a[i].fi, i};
	}
	
	sort(b, b + cc);
	
	if(!cc)
		return;
	
	segt.init(1, 1, n);
	
	ll num = b[cc - 1].se;
	
	segt.update(1, 1, n, a[num].fi, min(a[num].se, a[num].fi + K - 1), a[num].se, num);
	
	for(ll i = cc - 2 ; i >= 0 ; i--)
	{
		num = b[i].se;
		
		pair<pll, pll> qry = segt.query(1, 1, n, a[num].fi, a[num].se);

		if(qry.fi.se && a[num].se < qry.fi.fi)
			Rspa[num][0] = qry.fi.se;
		
		segt.update(1, 1, n, a[num].fi, min(a[num].se, a[num].fi + K - 1), a[num].se, num);
	}
}

void LL(void)
{
	ll cc = 0;
	
	for(ll i = 1 ; i <= m ; i++)
	{
		if(a[i].fi > a[i].se)
			b[cc++] = {a[i].fi, i};
	}
	
	sort(b, b + cc);
	reverse(b, b + cc);
	
	if(!cc)
		return;
	
	segt2.init(1, 1, n);
	
	ll num = b[cc - 1].se;
	
	segt2.update(1, 1, n, max(a[num].fi - K + 1, a[num].se), a[num].fi, a[num].se, num);
	
	for(ll i = cc - 2 ; i >= 0 ; i--)
	{
		num = b[i].se;

		pair<pll, pll> qry = segt2.query(1, 1, n, a[num].se, a[num].fi);

		if(qry.se.se && a[num].se > qry.se.fi)
			Lspa[num][0] = qry.se.se;

		segt2.update(1, 1, n, max(a[num].fi - K + 1, a[num].se), a[num].fi, a[num].se, num);
	}
}

void RL(void)
{
	ll cc = 0;
	vector<pll> vv;
	
	for(ll i = 1 ; i <= m ; i++)
	{
		if(a[i].fi < a[i].se)
			b[cc++] = {a[i].fi, i};
		else
			vv.push_back({a[i].fi, i});
	}

	sort(b, b + cc);
	reverse(b, b + cc);
	sort(vv.begin(), vv.end());
	reverse(vv.begin(), vv.end());
	segt.init(1, 1, n);

	ll p = 0;

	for(ll i = 0 ; i < cc ; i++)
	{
		ll num = b[i].se;

		while(p < (ll)vv.size() && vv[p].fi > min(a[num].fi + K - 1, a[num].se))
		{
			ll num2 = vv[p].se;

			segt.update(1, 1, n, vv[p].fi, a[num2].fi, a[num2].se, num2);
			p++;
		}

		pair<pll, pll> qry = segt.query(1, 1, n, a[num].fi, a[num].se);
		
		if(qry.se.se) //hmm...?
			Lspa[num][0] = qry.se.se;
	}
}

void LR(void)
{
	ll cc = 0;
	vector<pll> vv;
	
	for(ll i = 1 ; i <= m ; i++)
	{
		if(a[i].fi > a[i].se)
			b[cc++] = {a[i].fi, i};
		else
			vv.push_back({a[i].fi, i});
	}

	sort(b, b + cc);
	sort(vv.begin(), vv.end());
	segt.init(1, 1, n);

	ll p = 0;

	for(ll i = 0 ; i < cc ; i++)
	{
		ll num = b[i].se;

		while(p < (ll)vv.size() && vv[p].fi < max(a[num].se, a[num].fi - K + 1))
		{
			ll num2 = vv[p].se;
			
			segt.update(1, 1, n, a[num2].fi, vv[p].fi, a[num2].se, num2);
			p++;
		}

		pair<pll, pll> qry = segt.query(1, 1, n, a[num].se, a[num].fi);
		
		if(qry.fi.se) //hmm...?
			Rspa[num][0] = qry.fi.se;
	}
}

int main(void)
{
	fastio
	
	cin >> n >> K;
	cin >> m;
	
	for(ll i = 1 ; i <= m ; i++)
		cin >> a[i].fi >> a[i].se;
	
	LR();
	RL();
	LL();
	RR();

	for(ll i = 1 ; i <= m ; i++)
	{
		if(!Lspa[i][0])
			Lspa[i][0] = i;

		if(!Rspa[i][0])
			Rspa[i][0] = i;
	}

	for(ll i = 1 ; i <= 20 ; i++)
	{
		for(ll j = 1 ; j <= m ; j++)
		{
			if(a[Lspa[Lspa[j][i - 1]][i - 1]].se < a[Lspa[Rspa[j][i - 1]][i - 1]].se)
				Lspa[j][i] = Lspa[Lspa[j][i - 1]][i - 1];
			else
				Lspa[j][i] = Lspa[Rspa[j][i - 1]][i - 1];

			if(a[Rspa[Lspa[j][i - 1]][i - 1]].se > a[Rspa[Rspa[j][i - 1]][i - 1]].se)
				Rspa[j][i] = Rspa[Lspa[j][i - 1]][i - 1];
			else
				Rspa[j][i] = Rspa[Rspa[j][i - 1]][i - 1];
		}
	}

	cin >> q;

	while(q--)
	{
		cin >> L >> R;

		pair<pll, pll> num = segt.query(1, 1, n, L, L);
		pair<pll, pll> num2 = segt2.query(1, 1, n, L, L);

		if(L < R)
		{
			if(R <= num.fi.fi)
			{
				cout << 1 en;
				continue;
			}
		}

		else
		{
			if(R >= num2.se.fi)
			{
				cout << 1 en;
				continue;
			}
		}

		ll ans = 1;
		ll nR = num.fi.se;
		ll nL = num2.se.se;

		if(!nL && !nR)
		{
			cout << -1 en;
			continue;
		}

		for(ll i = 20 ; i >= 0 ; i--)
		{
			ll LL = INF, nxtL = 0;
			ll RR = -INF, nxtR = 0;

			if(nL)
			{
				if(LL > a[Lspa[nL][i]].se)
				{
					LL = a[Lspa[nL][i]].se;
					nxtL = Lspa[nL][i];
				}

				if(RR < a[Rspa[nL][i]].se)
				{
					RR = a[Rspa[nL][i]].se;
					nxtR = Rspa[nL][i];
				}
			}
			
			if(nR)
			{
				if(LL > a[Lspa[nR][i]].se)
				{
					LL = a[Lspa[nR][i]].se;
					nxtL = Lspa[nR][i];
				}

				if(RR < a[Rspa[nR][i]].se)
				{
					RR = a[Rspa[nR][i]].se;
					nxtR = Rspa[nR][i];
				}
			}

			if(L <= R && R <= RR)
				continue;

			if(R <= L && LL <= R)
				continue;

			ans += (1LL << i);
			nL = nxtL;
			nR = nxtR;
		}

		ll ff = 0;

		for(ll i = 0 ; i >= 0 ; i--)
		{
			ll LL = INF;
			ll RR = -INF;

			if(nL)
			{
				if(LL > a[Lspa[nL][i]].se)
					LL = a[Lspa[nL][i]].se;

				if(RR < a[Rspa[nL][i]].se)
					RR = a[Rspa[nL][i]].se;
			}
			
			if(nR)
			{
				if(LL > a[Lspa[nR][i]].se)
					LL = a[Lspa[nR][i]].se;

				if(RR < a[Rspa[nR][i]].se)
					RR = a[Rspa[nR][i]].se;
			}

			if(L <= R && R <= RR)
				ff = 1;

			if(R <= L && LL <= R)
				ff = 1;
		}

		if(!ff)
			cout << -1 en;
		else
			cout << ans + 1 en;
	}

	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 628 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 5 ms 1492 KB Output is correct
14 Correct 5 ms 1364 KB Output is correct
15 Correct 3 ms 1364 KB Output is correct
16 Correct 6 ms 1656 KB Output is correct
17 Correct 7 ms 1612 KB Output is correct
18 Correct 4 ms 1616 KB Output is correct
19 Correct 6 ms 1620 KB Output is correct
20 Correct 5 ms 1492 KB Output is correct
21 Correct 4 ms 1620 KB Output is correct
22 Correct 6 ms 1620 KB Output is correct
23 Incorrect 5 ms 1620 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 62272 KB Output is correct
2 Correct 254 ms 62488 KB Output is correct
3 Correct 319 ms 67424 KB Output is correct
4 Correct 218 ms 60596 KB Output is correct
5 Correct 724 ms 103912 KB Output is correct
6 Correct 630 ms 103884 KB Output is correct
7 Correct 371 ms 103892 KB Output is correct
8 Correct 394 ms 68604 KB Output is correct
9 Correct 402 ms 68764 KB Output is correct
10 Correct 617 ms 103808 KB Output is correct
11 Correct 624 ms 103892 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 62532 KB Output is correct
2 Correct 795 ms 104044 KB Output is correct
3 Correct 357 ms 68972 KB Output is correct
4 Correct 415 ms 103936 KB Output is correct
5 Correct 863 ms 103932 KB Output is correct
6 Correct 806 ms 103540 KB Output is correct
7 Incorrect 695 ms 104020 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 93292 KB Output is correct
2 Correct 390 ms 61540 KB Output is correct
3 Correct 227 ms 43432 KB Output is correct
4 Correct 128 ms 32480 KB Output is correct
5 Correct 98 ms 26920 KB Output is correct
6 Correct 69 ms 25132 KB Output is correct
7 Correct 238 ms 61112 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 5 ms 1492 KB Output is correct
10 Correct 652 ms 89028 KB Output is correct
11 Correct 726 ms 94424 KB Output is correct
12 Correct 671 ms 96688 KB Output is correct
13 Correct 684 ms 96584 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 5 ms 1492 KB Output is correct
16 Correct 458 ms 89116 KB Output is correct
17 Correct 592 ms 97332 KB Output is correct
18 Correct 564 ms 97348 KB Output is correct
19 Correct 538 ms 96576 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 628 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 5 ms 1492 KB Output is correct
14 Correct 5 ms 1364 KB Output is correct
15 Correct 3 ms 1364 KB Output is correct
16 Correct 6 ms 1656 KB Output is correct
17 Correct 7 ms 1612 KB Output is correct
18 Correct 4 ms 1616 KB Output is correct
19 Correct 6 ms 1620 KB Output is correct
20 Correct 5 ms 1492 KB Output is correct
21 Correct 4 ms 1620 KB Output is correct
22 Correct 6 ms 1620 KB Output is correct
23 Incorrect 5 ms 1620 KB Output isn't correct
24 Halted 0 ms 0 KB -