Submission #240600

#	Time	Username	Problem	Language	Result	Execution time	Memory
240600		sven	Sweeping (JOI20_sweeping)	C++14	10 / 100	9414 ms	250256 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;
struct Point
{
	int x , y , moment;
};



vector <Point> points;
vector <vector<int> > questions;
map<int , int> correspond;
map<int , int> inverse;

const int MAXN = (1<<21);

int arbre[MAXN * 2];

void mettre(int noeud , int val)
{
	noeud += MAXN;
	while (noeud > 0)
	{
		arbre[noeud] = max(arbre[noeud] , val);
		noeud/=2;
	}
}

int demander(int gauche , int droite)
{
	droite += MAXN;
	gauche += MAXN;
	int maxi = -1;
	while (gauche <= droite)
	{
		if (gauche % 2 == 1)
		{
			maxi = max(maxi , arbre[gauche]);
			gauche++;
		}
		if (droite % 2 == 0)
		{
			maxi = max(maxi , arbre[droite]);
			droite--;
		}
		gauche/=2;
		droite/=2;
	}
	return maxi;
}
int main()
{
	for (int i = 0 ; i < MAXN * 2 ; i++)
	{
		arbre[i] = -1;
	}
	int taille , nbPoints , nbQuestions;
	cin >> taille >> nbPoints >> nbQuestions;

	set<int> posY;
	posY.insert(taille);
	for (int i = 0 ; i < nbPoints ; i++)
	{
		points.push_back({0 , 0 ,0});
		cin >> points[i].x >> points[i].y;
		points[i].moment = 0;
		posY.insert(points[i].y);
	}
	for (int i = 0 ; i < nbQuestions ; i++)
	{
		int T;
		cin >> T;
		if (T == 4)
		{
			int a,b;
			cin >> a >> b;
			questions.push_back({T,a,b});
			posY.insert(b);
		}
		else
		{
			int a;
			cin >> a;
			questions.push_back({T,a});
			if (T == 2) posY.insert(a);
		}
	}
	auto it = posY.begin();
	int in = 0;
	while (it != posY.end())
	{
		auto actu = *it;
		correspond[actu] = in;
		inverse[in] = actu;
		in++;
		it++;
	}
	for (int iQ = 0 ; iQ < nbQuestions ; iQ++)
	{
		if (questions[iQ][0] == 4)
		{
			nbPoints++;
			points.push_back({questions[iQ][1] , questions[iQ][2] , iQ + 1});
		}
		else if (questions[iQ][0] == 1)
		{
			int droite = correspond[taille];
			int id = questions[iQ][1] - 1;
			int gauche = correspond[points[id].y];
			int meilleur = 1e9;
			while (gauche <= droite)
			{
				int milieu = (gauche + droite) / 2;
				if (demander(correspond[points[id].y] , milieu) >=points[id].moment)
				{
					meilleur= min(meilleur , milieu);
					droite = milieu - 1;
				}
				else
				{
					gauche = milieu + 1;
				}
			}
			if (meilleur == 1e9)
			{
				cout<<points[id].x<<" "<<points[id].y<<endl;
			}
			else
			{
				cout<<max(points[id].x , taille - inverse[meilleur])<<" "<<points[id].y<<endl;
			}
		}
		else
		{
			mettre(correspond[questions[iQ][1]] , iQ + 1);
		}
	}
}

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