oj.uz

답안 #125056

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125056 2019-07-04T14:00:31 Z hugo_pm Long Mansion (JOI17_long_mansion) C++17
0 / 100
 1225 ms 52224 KB 
#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];
				int oth = li[iElem];
				chmin(li[iElem], li[oth]);
				chmax(ri[iElem], ri[oth]);
			}
			else if (conRight[ri[iElem]] >= li[iElem]) {
				++ri[iElem];
				int oth = ri[iElem];
				chmin(li[iElem], li[oth]);
				chmax(ri[iElem], ri[oth]);
			}
			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";
		}
	}
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 39928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 39928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1225 ms 52224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 39928 KB Output isn't correct
2 Halted 0 ms 0 KB -