Submission #824183

#	Time	Username	Problem	Language	Result	Execution time	Memory
824183		sven	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	482 ms	43360 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1<<17;
const int MAXP = 19;

int droite[MAXN];
int gauche[MAXN];

struct inter
{
	int deb,fin;
	bool operator == (const inter & autre) const
	{
		return deb == autre.deb && fin == autre.fin;
	}
};

inter vide = {-1 , -1};

struct prQ
{
	int val , pos;
};

inter union_inter(inter a , inter b)
{
	if (a == vide) return b;
	if (b == vide) return a;
	return {min(a.deb , b.deb) , max(a.fin , b.fin)};
}

inter intervalles[MAXN * 2][MAXP];

void init()
{
	for (int i = 0 ; i < MAXN * 2 ; i++)
	{
		for (int j = 0 ; j < MAXP ; j++)
		{
			intervalles[i][j] = vide;
		}
	}
}

void remplir_etage(int et)
{
	for (int i = MAXN- 1 ; i > 0 ; i--)
	{
		intervalles[i][et] = union_inter(intervalles[i * 2][et] , intervalles[i * 2 + 1][et]);
	}
}

inter maxi(int deb , int fin , int et)
{
	deb += MAXN;
	fin += MAXN;
	inter rep = vide;	
	while (deb <= fin)
	{
		if (deb % 2 == 1)
		{
			rep = union_inter(rep , intervalles[deb][et]);
			deb++;
		}
		if (fin % 2 == 0)
		{
			rep = union_inter(rep , intervalles[fin][et]);
			fin--;
		}
		deb/=2;
		fin/=2;
	}
	return rep;
}

bool contient (inter a , int b)
{
	return a.deb <= b && a.fin >= b;
}
int main()
{
	init();
	int N , K;
	cin >> N >> K;
	int M;
	cin >> M;
	for (int i = 0 ; i < MAXN ; i++)
	{
		droite[i] = -1;
		gauche[i] = -1;
	}
	for (int i = 0 ; i < M ; i++)
	{
		int a,b;
		cin >> a >> b;
		a--; b--;
		if (a < b)
		{
			droite[a] = max(droite[a] , b);
		}
		else
		{
			if (gauche[a] == -1) gauche[a] = b;
			else gauche[a] = min(gauche[a] , b);
		}
	}

	deque<prQ> Q;
	for (int i = 0 ; i < N ; i++)
	{
		if (droite[i] != -1)
		{
			while (!Q.empty() && Q.front().val <= droite[i])
				Q.pop_front();
			Q.push_front({droite[i] , i});
		}
		while (!Q.empty() && Q.back().pos + K <= i)
			Q.pop_back();
		
		if (Q.empty())
			intervalles[i + MAXN][0].fin = i;
		else
			intervalles[i + MAXN][0].fin = max(i , Q.back().val);
	}
	Q.clear();
	for (int i = N - 1 ; i >= 0 ; i--)
	{
		if (gauche[i] != -1)
		{
			while (!Q.empty() && Q.front().val >= gauche[i])
				Q.pop_front();
			Q.push_front({gauche[i] , i});
		}
		while (!Q.empty() && Q.back().pos - K >= i)
			Q.pop_back();
		if (Q.empty())
			intervalles[i + MAXN][0].deb = i;
		else
		{
	//		cout<<"A"<<i<<" "<<Q.back().pos<<endl;
			intervalles[i + MAXN][0].deb = min(i , Q.back().val);
		}
	}
	/*for (int i = 0 ; i < N ; i++)
	{
		cout<<intervalles[i + MAXN][0].deb<<" "<<intervalles[i + MAXN][0].fin<<endl;
	}*/
	remplir_etage(0);
	for (int iP = 1 ; iP < MAXP ; iP++)
	{
		for (int i = 0 ; i < N ; i++)
		{
			intervalles[i + MAXN][iP] = maxi(intervalles[i + MAXN][iP - 1].deb , intervalles[i + MAXN][iP - 1].fin , iP - 1);	
		}
		remplir_etage(iP);
	}
	
	





	int nbQ;
	cin >> nbQ;
	for (int i = 0 ; i < nbQ ; i++)
	{
		int s,t;
		cin >> s >> t;
		s--; t--;
		inter tout = maxi(s , s , MAXP - 1);
		if (!contient(tout , t)) {cout<<-1<<endl; continue;}
		if (s == t) {cout<<0<<endl; continue;}
		int rep = 0;
		inter actu = {s , s};
		for (int iP = MAXP - 1 ; iP >= 0 ; iP--)
		{
			inter in = maxi(actu.deb , actu.fin , iP);
			if (!contient(in , t))
			{
				actu = in;
				rep += 1<<iP;
			}
		}
		cout<<rep + 1<<endl;
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13