oj.uz

Submission #795762

# Submission time Handle Problem Language Result Execution time Memory
795762 2023-07-27T14:30:49 Z denniskim Railway Trip 2 (JOI22_ho_t4) C++17
35 / 100
 488 ms 108132 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};

		lazy[no << 1][0] = {-INF, 0};
		lazy[no << 1][1] = {INF, 0};
		seg[no << 1][0] = {-INF, 0};
		seg[no << 1][1] = {INF, 0};

		lazy[no << 1 | 1][0] = {-INF, 0};
		lazy[no << 1 | 1][1] = {INF, 0};
		seg[no << 1 | 1][0] = {-INF, 0};
		seg[no << 1 | 1][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(lazy[no][0].se)
		{
			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(lazy[no][1].se)
		{
			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)
		{
			lazy[no][0] = lazy[no][1] = {v1, v2};
			prop(no, s, e);
			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][0].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;

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;
	
	segt.init(1, 1, n);
	
	ll num = b[cc - 1].se;
	
	segt.update(1, 1, n, a[num].se, max(a[num].fi, a[num].se - K + 1), a[num].fi, num);
	
	for(ll i = cc - 2 ; i >= 0 ; i--)
	{
		num = b[i].se;
		
		pair<pll, pll> qry = segt.query(1, 1, n, a[num].se, a[num].fi);
		
		if(qry.se.se)
			Lspa[num][0] = qry.se.se;
		
		segt.update(1, 1, n, a[num].se, max(a[num].fi, a[num].se - K + 1), a[num].fi, num);
	}
}

int main(void)
{
	fastio
	
	cin >> n >> K;
	cin >> m;
	
	for(ll i = 1 ; i <= m ; i++)
		cin >> a[i].fi >> a[i].se;
	
	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++)
			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);
		
		if(!num.fi.se)
		{
			cout << -1 en;
			continue;
		}

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

		ll ans = 1;

		for(ll i = 20 ; i >= 0 ; i--)
		{
			if(a[Rspa[num.fi.se][i]].se < R)
			{
				ans += (1LL << i);
				num.fi.se = Rspa[num.fi.se][i];
			}
		}

		if(a[Rspa[num.fi.se][0]].se < R)
		{
			cout << -1 en;
			continue;
		}

		cout << ans + 1 en;
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 61984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 148 ms 61204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 105324 KB Output is correct
2 Correct 190 ms 69452 KB Output is correct
3 Correct 118 ms 51420 KB Output is correct
4 Correct 95 ms 40652 KB Output is correct
5 Correct 63 ms 35112 KB Output is correct
6 Correct 43 ms 33700 KB Output is correct
7 Correct 128 ms 69172 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 3 ms 1492 KB Output is correct
10 Correct 369 ms 105064 KB Output is correct
11 Correct 483 ms 105192 KB Output is correct
12 Correct 409 ms 107980 KB Output is correct
13 Correct 417 ms 107680 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 3 ms 1620 KB Output is correct
16 Correct 251 ms 107468 KB Output is correct
17 Correct 343 ms 108120 KB Output is correct
18 Correct 300 ms 108132 KB Output is correct
19 Correct 286 ms 108080 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 644 KB Output isn't correct
2 Halted 0 ms 0 KB -