Submission #108921

#	Time	Username	Problem	Language	Result	Execution time	Memory
108921		hugo_pm	Two Antennas (JOI19_antennas)	C++17	100 / 100	1183 ms	64124 KiB

antennas

#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 = 10000000000000000LL;

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

const int borne = 201*1000;
int nbAntennes, nbRequetes;

struct Antenne
{
	int hauteur, rgDeb, rgFin;
};

struct Requete
{
	int deb=0, fin=0, rep=-1;
};

vector<Antenne> ants;
vector<Requete> requetes;


// Segtree

int stOrig[4*borne];
int stCool[4*borne]; // Une nomenclature de qualité
int lazy[4*borne];

void pushCool(int nod) // A VERIFIER
{
	if (lazy[nod] != BIG) {
		chmax(stCool[nod], stOrig[nod] - lazy[nod]);
		//cout << nod << " " << stOrig[nod] << " " << lazy[nod] << " => " << stOrig[nod] - lazy[nod] << "\n";
	}

	if (2*nod+1 < 4*borne) {
		chmin(lazy[2*nod], lazy[nod]);
		chmin(lazy[2*nod+1], lazy[nod]);
	}

	lazy[nod] = BIG;
}

void updOrig(int nod, int lno, int rno, int pos, int val)
{
	pushCool(nod); // A VERIFIER
	if (lno == rno) {
		assert(lno == pos);
		stOrig[nod] = val;
	} else {
		int midNo = (lno+rno) / 2;
		if (pos <= midNo) updOrig(2*nod, lno, midNo, pos, val);
		else updOrig(2*nod + 1, midNo+1, rno, pos, val);
		stOrig[nod] = max(stOrig[2*nod], stOrig[2*nod+1]);
	}
}

int getMaxCool(int nod, int lno, int rno, int li, int ri)
{
	pushCool(nod);
	if (lno > ri || rno < li) return -BIG;
	if (li <= lno && rno <= ri) return stCool[nod];
	int midNo = (lno+rno) / 2;

	int rd = max(getMaxCool(2*nod, lno, midNo, li, ri), getMaxCool(2*nod+1, midNo+1, rno, li, ri));
	return rd;
}

void updCool(int nod, int lno, int rno, int li, int ri, int delta)
{
	if (lno > ri || rno < li) return;
	if (li <= lno && rno <= ri) {
		chmin(lazy[nod], delta);
		pushCool(nod);
		return;
	}
	pushCool(nod);
	int midNo = (lno+rno) / 2;
	updCool(2*nod, lno, midNo, li, ri, delta);
	updCool(2*nod+1, midNo+1, rno, li, ri, delta);
	stCool[nod] = max(stCool[nod], max(stCool[2*nod], stCool[2*nod+1])); // A VERIFIER
}

// Fin segtree

vector<int> evAdd[borne];
vector<int> evDel[borne];
vector<int> evReq[borne];

void resoudre()
{
	fill_n(&stOrig[0], 4*borne, -BIG);
	fill_n(&stCool[0], 4*borne, -BIG);
	fill_n(&lazy[0], 4*borne, BIG);

	form(i, borne) { evAdd[i].clear(); evDel[i].clear(); evReq[i].clear(); }

	form(iReq, nbRequetes) {
		evReq[requetes[iReq].fin].push_back(iReq);
	}

	form(posAnt, nbAntennes) {
		Antenne &an = ants[posAnt];
		int posDeb = posAnt + an.rgDeb;
		if (posDeb >= nbAntennes) continue;
		int posFin = min(nbAntennes, posAnt + an.rgFin);

		evAdd[posDeb].push_back(posAnt);
		evDel[posFin].push_back(posAnt);
	}

	multiset<int> curHa;

	form(posAnt, nbAntennes) {

		for (int ev : evAdd[posAnt]) {
			updOrig(1, 0, nbAntennes-1, ev, ants[ev].hauteur);
		}

		Antenne &an = ants[posAnt];
		int rgDeb = max(0LL, posAnt - an.rgFin);
		int rgFin = posAnt - an.rgDeb;
		if (rgFin >= rgDeb) {
			updCool(1, 0, nbAntennes-1, rgDeb, rgFin, an.hauteur);
		}

		for (int ev : evReq[posAnt]) { // A VERIFIER : sur de l'ordre ?
			Requete &rq = requetes[ev];
			assert(rq.fin == posAnt);
			chmax(rq.rep, getMaxCool(1, 0, nbAntennes-1, rq.deb, rq.fin));
		}

		for (int ev : evDel[posAnt]) {
			updOrig(1, 0, nbAntennes-1, ev, -BIG);
		}
	}
}

void solve()
{
	cin >> nbAntennes;
	ants.resize(nbAntennes);

	form(iAnt, nbAntennes) {
		Antenne &an = ants[iAnt];
		cin >> an.hauteur >> an.rgDeb >> an.rgFin;
	}

	cin >> nbRequetes;
	requetes.resize(nbRequetes);

	form(iReq, nbRequetes) {
		cin >> requetes[iReq].deb >> requetes[iReq].fin;
		--requetes[iReq].deb;
		--requetes[iReq].fin;
		requetes[iReq].rep = -1;
	}

	resoudre();
	
	reverse(ants.begin(), ants.end());

	form(iReq, nbRequetes) {
		int newDeb = (nbAntennes - 1) - requetes[iReq].fin;
		int newFin = (nbAntennes - 1) - requetes[iReq].deb;
		
		requetes[iReq].deb = newDeb;
		requetes[iReq].fin = newFin;
	}

	resoudre();

	form(iReq, nbRequetes) cout << requetes[iReq].rep << "\n";
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65