Submission #795748

#	Time	Username	Problem	Language	Result	Execution time	Memory
795748		denniskim	Railway Trip 2 (JOI22_ho_t4)	C++17	0 / 100	433 ms	105324 KiB

Main

#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 != 0)
		{
			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 != 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)
		{
			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)
			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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13