oj.uz

Submission #795825

# Submission time Handle Problem Language Result Execution time Memory
795825 2023-07-27T16:42:34 Z denniskim Railway Trip 2 (JOI22_ho_t4) C++17
46 / 100
 1091 ms 106696 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({max(a[i].se, a[i].fi - K + 1), 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 >= a[num].fi)
		{
			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({min(a[i].se, a[i].fi + K - 1), 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 <= a[num].fi)
		{
			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;
		
		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;

		/*ll LL = L, RR = L;

		while(1)
		{
			cout << LL sp << RR en;

			if(LL <= R && R <= RR)
				break;

			ll minn = INF, maxx = -INF;

			for(ll i = 1 ; i <= m ; i++)
			{
				if(LL <= a[i].fi && a[i].fi <= RR)
				{
					minn = min(minn, a[i].se);
					maxx = max(maxx, a[i].se);
				}
			}

			LL = min(LL, minn);
			RR = max(RR, maxx);
		}*/
	}

	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 580 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 584 KB Output is correct
12 Incorrect 2 ms 596 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 580 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 584 KB Output is correct
12 Incorrect 2 ms 596 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 62796 KB Output is correct
2 Correct 311 ms 63152 KB Output is correct
3 Correct 309 ms 68464 KB Output is correct
4 Correct 215 ms 61312 KB Output is correct
5 Correct 887 ms 106072 KB Output is correct
6 Correct 649 ms 106060 KB Output is correct
7 Correct 353 ms 105792 KB Output is correct
8 Correct 511 ms 69612 KB Output is correct
9 Correct 461 ms 69704 KB Output is correct
10 Correct 651 ms 106044 KB Output is correct
11 Correct 679 ms 106068 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 62952 KB Output is correct
2 Correct 954 ms 106696 KB Output is correct
3 Correct 406 ms 70412 KB Output is correct
4 Correct 436 ms 106304 KB Output is correct
5 Correct 1091 ms 106644 KB Output is correct
6 Correct 1060 ms 106216 KB Output is correct
7 Incorrect 824 ms 106688 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 810 ms 93912 KB Output is correct
2 Correct 449 ms 62100 KB Output is correct
3 Correct 248 ms 44196 KB Output is correct
4 Correct 147 ms 33072 KB Output is correct
5 Correct 92 ms 27292 KB Output is correct
6 Correct 76 ms 25560 KB Output is correct
7 Correct 220 ms 61668 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 7 ms 1492 KB Output is correct
10 Correct 648 ms 89736 KB Output is correct
11 Correct 775 ms 95008 KB Output is correct
12 Correct 799 ms 97448 KB Output is correct
13 Correct 795 ms 97384 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 5 ms 1488 KB Output is correct
16 Correct 491 ms 89924 KB Output is correct
17 Correct 608 ms 98172 KB Output is correct
18 Correct 699 ms 98076 KB Output is correct
19 Correct 618 ms 97312 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 592 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 580 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 584 KB Output is correct
12 Incorrect 2 ms 596 KB Output isn't correct
13 Halted 0 ms 0 KB -