| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 240645 |
2020-06-20T10:55:04 Z |
sven |
Sweeping (JOI20_sweeping) |
C++14 |
|
17525 ms |
65836 KB |
#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;*/
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4003 ms |
41752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17525 ms |
46004 KB |
Output is correct |
| 2 |
Correct |
13967 ms |
65836 KB |
Output is correct |
| 3 |
Correct |
12937 ms |
64364 KB |
Output is correct |
| 4 |
Correct |
12451 ms |
65336 KB |
Output is correct |
| 5 |
Correct |
10552 ms |
65160 KB |
Output is correct |
| 6 |
Correct |
14015 ms |
65552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17525 ms |
46004 KB |
Output is correct |
| 2 |
Correct |
13967 ms |
65836 KB |
Output is correct |
| 3 |
Correct |
12937 ms |
64364 KB |
Output is correct |
| 4 |
Correct |
12451 ms |
65336 KB |
Output is correct |
| 5 |
Correct |
10552 ms |
65160 KB |
Output is correct |
| 6 |
Correct |
14015 ms |
65552 KB |
Output is correct |
| 7 |
Incorrect |
9335 ms |
65592 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
