| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 240010 |
2020-06-17T17:18:04 Z |
GREGOIRELC |
Wall (IOI14_wall) |
C++14 |
|
11 ms |
6656 KB |
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include "wall.h"
using namespace std;
const int MAX_POS = 2e6;
const int TAILLE_MAX = 1e5 + 1;
const int MAX_NOEUD = 1 << 18;
const int MID = 1 << 17;
const int RACINE = 1;
struct Info
{
int deb, fin, haut, tp, tps;
bool operator<(const Info &other)
{
return deb < other.deb;
}
};
int segTreeAjout[MAX_NOEUD], segTreeRetire[MAX_NOEUD];
vector<Info> debutModif, finModif;
priority_queue<pair<int, int> > vuAjout[TAILLE_MAX], vuRetire[TAILLE_MAX];
void update(int pos, int segTree[], int val)
{
pos += MID;
segTree[pos] = val;
pos /= 2;
while(pos > 0)
{
segTree[pos] = max(segTree[pos * 2], segTree[pos * 2 + 1]);
pos /= 2;
}
}
int getMax(int noeud, int curDeb, int curFin, int deb, int fin, int segTree[])
{
//cout << noeud << endl;
if(deb > curFin || fin < curDeb)
{
return 0;
}
if(curDeb >= deb && curFin <= fin)
{
return segTree[noeud];
}
if(curDeb == curFin)
{
return 0;
}
int mid = (curDeb + curFin) / 2;
return max(getMax(noeud * 2, curDeb, mid, deb, fin, segTree), getMax(noeud * 2 + 1, mid + 1, curFin, deb, fin, segTree));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for(int iModif = 0; iModif < k; iModif++)
{
debutModif.push_back({left[iModif], right[iModif], height[iModif], op[iModif], iModif + 1});
finModif.push_back({right[iModif], right[iModif], height[iModif], op[iModif], iModif + 1});
}
sort(debutModif.begin(), debutModif.end());
sort(finModif.begin(), finModif.end());
int curDeb = 0, curFin = 0, curHauteur = 0;
for(int curPos = 0; curPos < n; curPos++)
{
vector<int> aTester;
aTester.push_back(curHauteur);
//cout << 1 << endl;
for(; (curDeb < k) && (debutModif[curDeb].deb) <= curPos; curDeb++)
{
int deb = debutModif[curDeb].deb, fin = debutModif[curDeb].fin;
int haut = debutModif[curDeb].haut, tp = debutModif[curDeb].tp, tps = debutModif[curDeb].tps;
aTester.push_back(haut);
//cout << deb << " " << fin << " " << haut << " " << tp << " " << tps << endl;
//cout << 11 << " " << deb << endl;
if(tp == 1)
{
vuAjout[haut].push({tps, fin});
while(vuAjout[haut].top().second < curPos)
{
vuAjout[haut].pop();
}
update(haut, segTreeAjout, vuAjout[haut].top().first);
}
else
{
vuRetire[haut].push({tps, fin});
while(vuRetire[haut].top().second < curPos)
{
vuRetire[haut].pop();
}
update(haut, segTreeRetire, vuRetire[haut].top().first);
}
}
//cout << 2 << endl;
for(; (curFin < k) && (finModif[curFin].deb < curPos); curFin++)
{
int fin = finModif[curFin].deb;
int haut = finModif[curFin].haut, tp = finModif[curFin].tp, tps = finModif[curFin].tps;
aTester.push_back(haut);
//cout << fin << " " << haut << " " << tp << " " << tps << endl;
if(tp == 1)
{
while(!vuAjout[haut].empty() && vuAjout[haut].top().second < curPos)
{
vuAjout[haut].pop();
}
int val = 0;
if(!vuAjout[haut].empty())
{
val = vuAjout[haut].top().first;
}
update(haut, segTreeAjout, val);
}
else
{
while(!vuRetire[haut].empty() && vuRetire[haut].top().second < curPos)
{
vuRetire[haut].pop();
}
int val = 0;
if(!vuRetire[haut].empty())
{
val = vuRetire[haut].top().first;
}
update(haut, segTreeRetire, val);
}
}
curHauteur = 0;
for(int haut = 1; haut <= 10000; haut++)
{
//cout << curPos << " " << haut << " " << getMax(RACINE, 0, MID - 1, 0, haut - 1, segTreeRetire) << " " << getMax(RACINE, 0, MID - 1, haut, MID - 1, segTreeAjout) << endl;
if(getMax(RACINE, 0, MID - 1, 0, haut - 1, segTreeRetire) < getMax(RACINE, 0, MID - 1, haut, MID - 1, segTreeAjout))
{
curHauteur = haut;
}
}
/*for(int haut : aTester)
{
//cout << haut << endl;
if(haut > 0 && getMax(RACINE, 0, MID - 1, 0, haut - 1, segTreeRetire) < getMax(RACINE, 0, MID - 1, haut, MID - 1, segTreeAjout))
{
curHauteur = max(curHauteur, haut);
}
if(haut > 1 && getMax(RACINE, 0, MID - 1, 0, haut-2, segTreeRetire) < getMax(RACINE, 0, MID - 1, haut-1, MID - 1, segTreeAjout))
{
curHauteur = max(curHauteur, haut - 1);
}
if(getMax(RACINE, 0, MID - 1, 0, haut, segTreeRetire) < getMax(RACINE, 0, MID - 1, haut + 1, MID - 1, segTreeAjout))
{
curHauteur = max(curHauteur, haut + 1);
}
}*/
finalHeight[curPos] = curHauteur;
}
}
Compilation message
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:76:8: warning: unused variable 'deb' [-Wunused-variable]
int deb = debutModif[curDeb].deb, fin = debutModif[curDeb].fin;
^~~
wall.cpp:103:8: warning: unused variable 'fin' [-Wunused-variable]
int fin = finModif[curFin].deb;
^~~
wall.cpp:104:64: warning: unused variable 'tps' [-Wunused-variable]
int haut = finModif[curFin].haut, tp = finModif[curFin].tp, tps = finModif[curFin].tps;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
6656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
6656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
6656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
6528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
