#include <bits/stdc++.h>
using namespace std;
#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)
#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second
const long long BIG = 1000000000000000000LL;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
void solve();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
// Version classique du segment tree
// Opérations en O(log N)
// Indices 0-indexés
class SegtreeClassic
{
public:
void init(vector<int> tab);
int requete(int gauche, int droite);
void modifier(int index, int val);
private:
const int UNDEF = 1e9 + 171;
int nbElements;
int combiner(int a, int b);
vector<int> interne;
};
void SegtreeClassic::init(vector<int> tab)
{
nbElements = tab.size();
interne.resize(2 * nbElements);
for (int ind = 0; ind < nbElements; ++ind)
interne[ind + nbElements] = tab[ind];
for (int ind = nbElements - 1; ind >= 0; --ind)
interne[ind] = combiner(interne[2*ind], interne[2*ind + 1]);
}
int SegtreeClassic::requete(int gauche, int droite)
{
int res = UNDEF;
++droite; // Pour passer à un intervalle semi-ouvert [l ; r[
gauche += nbElements;
droite += nbElements;
while (gauche < droite)
{
// Si gauche est impair, le noeud est inclus mais pas le parent
// On ajoute donc ce noeud et on passera plus tard au noeud à droite du parent
if (gauche & 1)
res = combiner(res, interne[gauche++]);
// Même raisonnement sachant que droite est exclus, d'où la {pré}-décrémentation
if (droite & 1)
res = combiner(res, interne[--droite]);
gauche /= 2;
droite /= 2;
}
return res;
}
void SegtreeClassic::modifier(int index, int val)
{
index += nbElements;
interne[index] = val;
index /= 2;
while (index > 0)
{
interne[index] = combiner(interne[2*index], interne[2*index+1]);
index /= 2;
}
}
int SegtreeClassic::combiner(int a, int b)
{
if (a == UNDEF) return b;
if (b == UNDEF) return a;
return min(a, b);
}
const int borne = 501*1000;
int nbElem, nbReq;
int reqKey[borne];
int conLeft[borne], conRight[borne];
vector<int> keyPos[borne];
vector<int> iniTab[borne];
int lastLigneDroite[borne];
int li[borne], ri[borne];
void solve()
{
cin >> nbElem;
form(i, nbElem-1) { cin >> reqKey[i]; }
form(iPos, nbElem) {
int nbKeys; cin >> nbKeys;
form(iRcp, nbKeys) {
int keyId; cin >> keyId;
keyPos[keyId].push_back(iPos);
iniTab[iPos].push_back(keyId);
}
}
conLeft[0] = BIG;
conRight[nbElem-1] = -BIG;
form(iElem, nbElem) {
if (iElem > 0) {
int keyToLeft = reqKey[iElem-1];
auto &listePos = keyPos[keyToLeft];
auto it = lower_bound(listePos.begin(), listePos.end(), iElem);
if (listePos.empty() || it == listePos.end()) {
conLeft[iElem] = BIG;
} else {
conLeft[iElem] = *it;
}
}
if (iElem+1 < nbElem) {
int keyToRight = reqKey[iElem];
auto &listePos = keyPos[keyToRight];
auto it = upper_bound(listePos.begin(), listePos.end(), iElem);
if (listePos.empty() || it == listePos.begin()) {
conRight[iElem] = -BIG;
} else {
--it;
conRight[iElem] = *it;
}
}
}
vector<int> lstPos(borne, nbElem-1);
SegtreeClassic sc; sc.init(lstPos);
ford(iElem, nbElem) {
if (conRight[iElem] >= 0) sc.modifier(conRight[iElem]+1, iElem);
else sc.modifier(0, iElem);
lastLigneDroite[iElem] = sc.requete(0, iElem); // TODO A VERIFIER
}
li[0] = 0; ri[0] = lastLigneDroite[0];
form2(iElem, 1, nbElem) {
li[iElem] = iElem;
ri[iElem] = lastLigneDroite[iElem];
if (conLeft[iElem] <= ri[iElem]) {
li[iElem] = li[iElem-1];
chmax(ri[iElem], ri[iElem-1]);
}
while (true) {
if (conLeft[li[iElem]] <= ri[iElem]) {
--li[iElem];
chmin(li[iElem], li[li[iElem]]);
chmax(ri[iElem], ri[li[iElem]]);
}
else if (conRight[ri[iElem]] >= li[iElem]) {
++ri[iElem];
chmin(li[iElem], li[ri[iElem]]);
chmax(ri[iElem], ri[ri[iElem]]);
}
else break;
}
}
cin >> nbReq;
form(iReq, nbReq) {
int x, y; cin >> x >> y;
--x; --y;
if (li[x] <= y && y <= ri[x]) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
39800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
39800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1799 ms |
51680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
39800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
