oj.uz

Submission #240600

# Submission time Handle Problem Language Result Execution time Memory
240600 2020-06-20T08:38:56 Z sven Sweeping (JOI20_sweeping) C++14
10 / 100
 9414 ms 250256 KB 
#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.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9343 ms 250256 KB Output is correct
2 Correct 9118 ms 250240 KB Output is correct
3 Correct 9414 ms 250128 KB Output is correct
4 Correct 8054 ms 248656 KB Output is correct
5 Correct 8309 ms 249920 KB Output is correct
6 Correct 9183 ms 250000 KB Output is correct
7 Correct 9412 ms 250164 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

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