oj.uz

Submission #795842

# Submission time Handle Problem Language Result Execution time Memory
795842 2023-07-27T17:27:26 Z denniskim Railway Trip 2 (JOI22_ho_t4) C++17
54 / 100
 836 ms 104436 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 580 KB Output is correct
4 Correct 1 ms 596 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 584 KB Output is correct
8 Correct 1 ms 580 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 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 580 KB Output is correct
4 Correct 1 ms 596 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 584 KB Output is correct
8 Correct 1 ms 580 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 5 ms 1492 KB Output is correct
14 Correct 4 ms 1492 KB Output is correct
15 Correct 3 ms 1360 KB Output is correct
16 Correct 6 ms 1620 KB Output is correct
17 Correct 5 ms 1672 KB Output is correct
18 Correct 4 ms 1620 KB Output is correct
19 Correct 6 ms 1620 KB Output is correct
20 Correct 5 ms 1620 KB Output is correct
21 Correct 5 ms 1612 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 247 ms 62852 KB Output is correct
2 Correct 276 ms 62960 KB Output is correct
3 Correct 313 ms 67932 KB Output is correct
4 Correct 208 ms 61096 KB Output is correct
5 Correct 719 ms 104404 KB Output is correct
6 Correct 609 ms 104416 KB Output is correct
7 Correct 349 ms 104436 KB Output is correct
8 Correct 381 ms 69160 KB Output is correct
9 Correct 382 ms 69144 KB Output is correct
10 Correct 598 ms 104400 KB Output is correct
11 Correct 598 ms 104276 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 63008 KB Output is correct
2 Correct 799 ms 104236 KB Output is correct
3 Correct 344 ms 69216 KB Output is correct
4 Correct 449 ms 104204 KB Output is correct
5 Correct 836 ms 104224 KB Output is correct
6 Correct 799 ms 103796 KB Output is correct
7 Incorrect 682 ms 104256 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 703 ms 93920 KB Output is correct
2 Correct 364 ms 62128 KB Output is correct
3 Correct 221 ms 43928 KB Output is correct
4 Correct 143 ms 32760 KB Output is correct
5 Correct 82 ms 27116 KB Output is correct
6 Correct 70 ms 25436 KB Output is correct
7 Correct 232 ms 61644 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 5 ms 1492 KB Output is correct
10 Correct 649 ms 89824 KB Output is correct
11 Correct 691 ms 95064 KB Output is correct
12 Correct 678 ms 97288 KB Output is correct
13 Correct 703 ms 97036 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 5 ms 1492 KB Output is correct
16 Correct 445 ms 89788 KB Output is correct
17 Correct 595 ms 97896 KB Output is correct
18 Correct 547 ms 97808 KB Output is correct
19 Correct 537 ms 97008 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 580 KB Output is correct
4 Correct 1 ms 596 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 584 KB Output is correct
8 Correct 1 ms 580 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 5 ms 1492 KB Output is correct
14 Correct 4 ms 1492 KB Output is correct
15 Correct 3 ms 1360 KB Output is correct
16 Correct 6 ms 1620 KB Output is correct
17 Correct 5 ms 1672 KB Output is correct
18 Correct 4 ms 1620 KB Output is correct
19 Correct 6 ms 1620 KB Output is correct
20 Correct 5 ms 1620 KB Output is correct
21 Correct 5 ms 1612 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 -