Submission #125092

#	Time	Username	Problem	Language	Result	Execution time	Memory
125092		hugo_pm	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	639 ms	104996 KiB

long_mansion

#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], gt[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];

	vector<int> tmp(borne, 0);
	form(i, borne) tmp[i] = -lastLigneDroite[i];
	sc.init(tmp);

	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];
				chmax(ri[iElem], gt[li[iElem]]);
				chmin(li[iElem], li[li[iElem]]);
			}
			else if (conRight[ri[iElem]] >= li[iElem]) {
				++ri[iElem];
			}
			else break;
		}
		sc.modifier(iElem, -ri[iElem]);
		gt[iElem] = -sc.requete(li[iElem], iElem);
	}
 

	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";
		}
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75