Submission #240645

#	Time	Username	Problem	Language	Result	Execution time	Memory
240645		sven	청소 (JOI20_sweeping)	C++14	11 / 100	17525 ms	65836 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;

const int MAXN = (1<<19);

struct Point
{
	int x , y;
};

struct Query
{
	int T , l;
};


struct Noeud
{
	int mini ,maxi , change;
};

Noeud arbreX[MAXN * 2];
Noeud arbreY[MAXN * 2];



void updateX(int noeud)
{
	arbreX[noeud].mini = max(arbreX[noeud].mini , arbreX[noeud].change);
	arbreX[noeud].maxi = max(arbreX[noeud].maxi , arbreX[noeud].change);
	if (noeud < MAXN)
	{
		for (int i = 0 ; i < 2 ; i++)
		{
			arbreX[noeud * 2 + i].change = max(arbreX[noeud * 2 + i].change , arbreX[noeud].change);
		}
	}
	arbreX[noeud].change = 0;
}


pair<int , int> descendreX(int noeud , int debut , int fin , int debutCible , int finCible , int modif)
{
	updateX(noeud);
	if (debutCible <= debut && fin <= finCible)
	{
		arbreX[noeud].change = modif;
		updateX(noeud);
		return {arbreX[noeud].mini , arbreX[noeud].maxi};
	}
	else if (!(debut > finCible || fin < debutCible))
	{
		pair<int , int> r ,s;
		r = descendreX(noeud * 2 , debut , (debut + fin) / 2 , debutCible , finCible , modif);
		s = descendreX(noeud * 2 + 1 , (debut + fin) / 2 + 1 , fin , debutCible , finCible , modif);
		arbreX[noeud].mini = min(arbreX[noeud * 2].mini , arbreX[noeud * 2 + 1].mini);
		arbreX[noeud].maxi = max(arbreX[noeud * 2].maxi , arbreX[noeud * 2 + 1].maxi);

		return {min(r.first , s.first) , max(r.second , s.second)};
	}

	return {2e9 , -2e9};
}

int trouverX(int noeud , int debut , int fin , int cible)
{
	updateX(noeud);
	if (noeud < MAXN)
	{
		updateX(noeud * 2);
		updateX(noeud * 2 + 1);
	}
	if (noeud >= MAXN)
	{
		if (arbreX[noeud].mini <= cible) return noeud - MAXN;
		return -1;
	}
	if (arbreX[noeud * 2].mini <= cible)
	{
		return trouverX(noeud * 2 , debut , (debut + fin) / 2 , cible);
	}
	return trouverX(noeud * 2 + 1 , (debut + fin) / 2 , fin , cible);

}






void updateY(int noeud)
{
	arbreY[noeud].mini = max(arbreY[noeud].mini , arbreY[noeud].change);
	arbreY[noeud].maxi = max(arbreY[noeud].maxi , arbreY[noeud].change);
	if (noeud < MAXN)
	{
		for (int i = 0 ; i < 2 ; i++)
		{
			arbreY[noeud * 2 + i].change = max(arbreY[noeud * 2 + i].change , arbreY[noeud].change);
		}
	}
	arbreY[noeud].change = 0;
}


pair<int , int> descendreY(int noeud , int debut , int fin , int debutCible , int finCible , int modif)
{
	updateY(noeud);
	if (debutCible <= debut && fin <= finCible)
	{
		arbreY[noeud].change = modif;
		updateY(noeud);
		return {arbreY[noeud].mini , arbreY[noeud].maxi};
	}
	else if (!(debut > finCible || fin < debutCible))
	{
		pair<int , int> r ,s;
		r = descendreY(noeud * 2 , debut , (debut + fin) / 2 , debutCible , finCible , modif);
		s = descendreY(noeud * 2 + 1 , (debut + fin) / 2 + 1 , fin , debutCible , finCible , modif);
		arbreY[noeud].mini = min(arbreY[noeud * 2].mini , arbreY[noeud * 2 + 1].mini);
		arbreY[noeud].maxi = max(arbreY[noeud * 2].maxi , arbreY[noeud * 2 + 1].maxi);

		return {min(r.first , s.first) , max(r.second , s.second)};
	}

	return {2e9 , -2e9};
}

int trouverY(int noeud , int debut , int fin , int cible)
{
	updateY(noeud);
	if (noeud < MAXN)
	{
		updateY(noeud * 2);
		updateY(noeud * 2 + 1);
	}
	if (noeud >= MAXN)
	{
		if (arbreY[noeud].mini <= cible) return noeud - MAXN;
		return -1;
	}
	if (arbreY[noeud * 2].mini <= cible)
	{
		return trouverY(noeud * 2 , debut , (debut + fin) / 2 , cible);
	}
	return trouverY(noeud * 2 + 1 , (debut + fin) / 2 , fin , cible);

}






void afficherX(int noeud , int p)
{
	if (noeud < MAXN)
	{
		afficherX(noeud * 2 + 1 , p + 1);
	}
	for (int i = 0 ; i < p ; i++) cout<<"   ";
	cout<<arbreX[noeud].maxi<<" "<<arbreX[noeud].mini<<" "<<arbreX[noeud].change<<endl;
	if (noeud < MAXN)
	{
		afficherX(noeud * 2 , p + 1);
	}
}

void afficherY(int noeud , int p)
{
	if (noeud < MAXN)
	{
		afficherY(noeud * 2 + 1 , p + 1);
	}
	for (int i = 0 ; i < p ; i++) cout<<"   ";
	cout<<arbreY[noeud].maxi<<" "<<arbreY[noeud].mini<<" "<<arbreY[noeud].change<<endl;
	if (noeud < MAXN)
	{
		afficherY(noeud * 2 , p + 1);
	}
}

/*
set<int> posX;
set <int> posY;
map<int , int> correspondX;
map<int , int> correspondY;
map<int , int> inverseX;
map<int , int> inverseY;
*/

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int taille , nbPoints , nbQuestions;
	cin >> taille >> nbPoints >> nbQuestions;
	Point points[nbPoints];
	Query questions[nbQuestions];
	for (int i = 0 ; i < nbPoints ; i++)
	{
		cin >> points[i].x >> points[i].y;
		descendreX(1 , 0 , MAXN - 1 , i , i , points[i].x);
		descendreY(1 , 0 , MAXN - 1 , i , i , points[i].y);
		//posX.insert(points[i].x);
		//posY.insert(points[i].y);
	}
	for (int i = 0 ; i < nbQuestions ; i++)
	{
		int a,b;
		cin >> a >> b;
		questions[i] = {a,b};
		//if (a == 2) posY.insert(b);
		//if (a == 3) posX.insert(b);
	}

	/*auto it = posX.begin();
	int in = 0;
	while (it != posX.end())
	{
		auto actu = *it;
		correspondX[actu] = in;
		inverseX[in] = actu;
		in++;
		it++;
	}
	it= posY.begin();
	in = 0;
	while (it != posY.end())
	{
		auto actu = *it;
		correspondY[actu] = in;
		inverseY[in] = actu;
		in++;
		it++;
	}*/
//	afficherX(1 , 0);
//	afficherY(1 , 0);
	for (int iQ = 0 ; iQ < nbQuestions ; iQ++)
	{
		if (questions[iQ].T == 1)
		{
			cout<<descendreX(1 , 0 , MAXN - 1 , questions[iQ].l - 1 , questions[iQ].l - 1 , 0).second<<" "<<descendreY(1 , 0 , MAXN - 1 , questions[iQ].l - 1 , questions[iQ].l - 1 , 0).second<<endl;
			//trouver le point
		}
		else if (questions[iQ].T == 2)
		{
			int noeudBase = trouverY(1 , 0 , MAXN - 1 , questions[iQ].l);
			if (noeudBase == -1) continue;
			int gauche = 0;
			int droite = noeudBase;
			int mG = noeudBase;
			while (gauche <= droite)
			{
				int milieu = (gauche + droite) / 2;
				if (descendreY(1 , 0 , MAXN - 1 , milieu , noeudBase , 0).second <= questions[iQ].l)
				{
					mG = milieu;
					droite = milieu - 1;
				}
				else gauche = milieu + 1;
			}

			int mD = noeudBase;
			gauche = noeudBase;
			droite = nbPoints - 1;
			while (gauche <= droite)
			{
				int milieu = (gauche + droite) / 2;
				if (descendreY(1 , 0 , MAXN - 1 , noeudBase , milieu , 0).second <= questions[iQ].l)
				{
					mD = milieu;
					gauche = milieu + 1;
				}
				else droite = milieu - 1;
			}
	//		cout<<"eeeE"<<iQ<<" "<<mG<<" "<<mD<<" "<<descendreY(1 , 0 , MAXN - 1 , mG , mD , 0).second<<endl;
			descendreX(1 , 0 , MAXN - 1 , mG , mD , taille - questions[iQ].l);
		}
		else if (questions[iQ].T == 3)
		{
			int noeudBase = trouverX(1 , 0 , MAXN - 1 , questions[iQ].l);
			if (noeudBase == -1) continue;
			int gauche = 0;
			int droite = noeudBase;
			int mG = noeudBase;
			while (gauche <= droite)
			{
				int milieu = (gauche + droite) / 2;
				if (descendreX(1 , 0 , MAXN - 1 , milieu , noeudBase , 0).second <= questions[iQ].l)
				{
					mG = milieu;
					droite = milieu - 1;
				}
				else gauche = milieu + 1;
			}

			int mD = noeudBase;
			gauche = noeudBase;
			droite = nbPoints - 1;
			while (gauche <= droite)
			{
				int milieu = (gauche + droite) / 2;
				if (descendreX(1 , 0 , MAXN - 1 , noeudBase , milieu , 0).second <= questions[iQ].l)
				{
					mD = milieu;
					gauche = milieu + 1;
				}
				else droite = milieu - 1;
			}
			descendreY(1 , 0 , MAXN - 1 , mG , mD , taille - questions[iQ].l);
		}

	/*	cout<<endl;
		for (int i = 0 ; i < nbPoints ; i++)
		{
			cout<<descendreX(1 , 0 , MAXN - 1 ,i , i , 0).second<<" "<<descendreY(1 , 0 , MAXN - 1 , i, i , 0).second<<endl;

		}
		cout<<endl;*/
	}

}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25