#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, BIG);
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]]);
}
else if (conRight[ri[iElem]] >= li[iElem]) {
++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 |
Correct |
42 ms |
39900 KB |
Output is correct |
2 |
Correct |
44 ms |
39928 KB |
Output is correct |
3 |
Correct |
47 ms |
39928 KB |
Output is correct |
4 |
Correct |
42 ms |
39804 KB |
Output is correct |
5 |
Correct |
41 ms |
39856 KB |
Output is correct |
6 |
Correct |
42 ms |
39800 KB |
Output is correct |
7 |
Correct |
41 ms |
39860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
39900 KB |
Output is correct |
2 |
Correct |
44 ms |
39928 KB |
Output is correct |
3 |
Correct |
47 ms |
39928 KB |
Output is correct |
4 |
Correct |
42 ms |
39804 KB |
Output is correct |
5 |
Correct |
41 ms |
39856 KB |
Output is correct |
6 |
Correct |
42 ms |
39800 KB |
Output is correct |
7 |
Correct |
41 ms |
39860 KB |
Output is correct |
8 |
Correct |
154 ms |
39808 KB |
Output is correct |
9 |
Correct |
153 ms |
39888 KB |
Output is correct |
10 |
Correct |
156 ms |
39892 KB |
Output is correct |
11 |
Correct |
161 ms |
40056 KB |
Output is correct |
12 |
Correct |
141 ms |
39712 KB |
Output is correct |
13 |
Correct |
150 ms |
39864 KB |
Output is correct |
14 |
Correct |
149 ms |
39900 KB |
Output is correct |
15 |
Correct |
151 ms |
39900 KB |
Output is correct |
16 |
Correct |
225 ms |
39900 KB |
Output is correct |
17 |
Correct |
150 ms |
39900 KB |
Output is correct |
18 |
Correct |
151 ms |
39932 KB |
Output is correct |
19 |
Correct |
150 ms |
39904 KB |
Output is correct |
20 |
Correct |
160 ms |
39992 KB |
Output is correct |
21 |
Correct |
146 ms |
40088 KB |
Output is correct |
22 |
Correct |
149 ms |
39904 KB |
Output is correct |
23 |
Correct |
150 ms |
39928 KB |
Output is correct |
24 |
Correct |
150 ms |
39856 KB |
Output is correct |
25 |
Correct |
153 ms |
39884 KB |
Output is correct |
26 |
Correct |
154 ms |
39928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1176 ms |
53764 KB |
Output is correct |
2 |
Correct |
1843 ms |
53252 KB |
Output is correct |
3 |
Correct |
2148 ms |
52840 KB |
Output is correct |
4 |
Correct |
1422 ms |
53500 KB |
Output is correct |
5 |
Correct |
1546 ms |
53304 KB |
Output is correct |
6 |
Correct |
849 ms |
49384 KB |
Output is correct |
7 |
Correct |
320 ms |
49492 KB |
Output is correct |
8 |
Correct |
273 ms |
49296 KB |
Output is correct |
9 |
Correct |
281 ms |
49320 KB |
Output is correct |
10 |
Correct |
254 ms |
49192 KB |
Output is correct |
11 |
Correct |
253 ms |
49200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
39900 KB |
Output is correct |
2 |
Correct |
44 ms |
39928 KB |
Output is correct |
3 |
Correct |
47 ms |
39928 KB |
Output is correct |
4 |
Correct |
42 ms |
39804 KB |
Output is correct |
5 |
Correct |
41 ms |
39856 KB |
Output is correct |
6 |
Correct |
42 ms |
39800 KB |
Output is correct |
7 |
Correct |
41 ms |
39860 KB |
Output is correct |
8 |
Correct |
154 ms |
39808 KB |
Output is correct |
9 |
Correct |
153 ms |
39888 KB |
Output is correct |
10 |
Correct |
156 ms |
39892 KB |
Output is correct |
11 |
Correct |
161 ms |
40056 KB |
Output is correct |
12 |
Correct |
141 ms |
39712 KB |
Output is correct |
13 |
Correct |
150 ms |
39864 KB |
Output is correct |
14 |
Correct |
149 ms |
39900 KB |
Output is correct |
15 |
Correct |
151 ms |
39900 KB |
Output is correct |
16 |
Correct |
225 ms |
39900 KB |
Output is correct |
17 |
Correct |
150 ms |
39900 KB |
Output is correct |
18 |
Correct |
151 ms |
39932 KB |
Output is correct |
19 |
Correct |
150 ms |
39904 KB |
Output is correct |
20 |
Correct |
160 ms |
39992 KB |
Output is correct |
21 |
Correct |
146 ms |
40088 KB |
Output is correct |
22 |
Correct |
149 ms |
39904 KB |
Output is correct |
23 |
Correct |
150 ms |
39928 KB |
Output is correct |
24 |
Correct |
150 ms |
39856 KB |
Output is correct |
25 |
Correct |
153 ms |
39884 KB |
Output is correct |
26 |
Correct |
154 ms |
39928 KB |
Output is correct |
27 |
Correct |
1176 ms |
53764 KB |
Output is correct |
28 |
Correct |
1843 ms |
53252 KB |
Output is correct |
29 |
Correct |
2148 ms |
52840 KB |
Output is correct |
30 |
Correct |
1422 ms |
53500 KB |
Output is correct |
31 |
Correct |
1546 ms |
53304 KB |
Output is correct |
32 |
Correct |
849 ms |
49384 KB |
Output is correct |
33 |
Correct |
320 ms |
49492 KB |
Output is correct |
34 |
Correct |
273 ms |
49296 KB |
Output is correct |
35 |
Correct |
281 ms |
49320 KB |
Output is correct |
36 |
Correct |
254 ms |
49192 KB |
Output is correct |
37 |
Correct |
253 ms |
49200 KB |
Output is correct |
38 |
Correct |
559 ms |
75856 KB |
Output is correct |
39 |
Correct |
581 ms |
83372 KB |
Output is correct |
40 |
Correct |
525 ms |
68664 KB |
Output is correct |
41 |
Execution timed out |
3105 ms |
72768 KB |
Time limit exceeded |
42 |
Halted |
0 ms |
0 KB |
- |