Submission #788141

#	Time	Username	Problem	Language	Result	Execution time	Memory
788141		oscar1f	Two Antennas (JOI19_antennas)	C++17	100 / 100	592 ms	67316 KiB

antennas

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define int long long

const ll MAX_TAILLE=200*1000+5,INFINI=2*1000*1000*1000+5,DECA=(1<<18);

struct antenne{
	ll hauteur,minDist,maxDist;
};

struct som{
	ll deb,fin,minProp,maxProp,maxi,valMin,valMax;
};

ll taille,nbReq,debReq,finReq;
antenne ant[MAX_TAILLE];
vector<ll> ajout[MAX_TAILLE],suppre[MAX_TAILLE];
vector<pair<ll,ll>> reqFin[MAX_TAILLE];
som maxDiff[2*DECA];
ll rep[MAX_TAILLE];

void prepa(int pos,int debInter,int finInter) {
	maxDiff[pos].deb=debInter;
	maxDiff[pos].fin=finInter;
	maxDiff[pos].minProp=INFINI;
	maxDiff[pos].maxProp=-INFINI;
	maxDiff[pos].maxi=-1;
	maxDiff[pos].valMin=INFINI;
	maxDiff[pos].valMax=-INFINI;
	if (debInter!=finInter) {
		int midInter=(debInter+finInter)/2;
		prepa(2*pos,debInter,midInter);
		prepa(2*pos+1,midInter+1,finInter);
	}
}

void pushFlag(int pos) {
	if (maxDiff[pos].minProp!=INFINI and maxDiff[pos].valMax!=-INFINI) {
		maxDiff[pos].maxi=max(maxDiff[pos].maxi,abs(maxDiff[pos].minProp-maxDiff[pos].valMax));
	}
	if (maxDiff[pos].maxProp!=-INFINI and maxDiff[pos].valMin!=INFINI) {
		maxDiff[pos].maxi=max(maxDiff[pos].maxi,abs(maxDiff[pos].maxProp-maxDiff[pos].valMin));
	}
	if (maxDiff[pos].deb!=maxDiff[pos].fin) {
		for (int i=0;i<2;i++) {
			maxDiff[2*pos+i].minProp=min(maxDiff[2*pos+i].minProp,maxDiff[pos].minProp);
			maxDiff[2*pos+i].maxProp=max(maxDiff[2*pos+i].maxProp,maxDiff[pos].maxProp);
		}
	}
	maxDiff[pos].minProp=INFINI;
	maxDiff[pos].maxProp=-INFINI;
}

void modifSommet(int pos,int idSom,int typeModif) {
	pushFlag(pos);
	if (maxDiff[pos].deb>idSom or maxDiff[pos].fin<idSom) {
		return;
	}
	if (maxDiff[pos].deb==maxDiff[pos].fin) {
		if (typeModif==0) {
			maxDiff[pos].valMin=INFINI;
			maxDiff[pos].valMax=-INFINI;
		}
		else {
			maxDiff[pos].valMin=ant[idSom].hauteur;
			maxDiff[pos].valMax=ant[idSom].hauteur;
		}
	}
	else {
		modifSommet(2*pos,idSom,typeModif);
		modifSommet(2*pos+1,idSom,typeModif);
		maxDiff[pos].valMin=min(maxDiff[2*pos].valMin,maxDiff[2*pos+1].valMin);
		maxDiff[pos].valMax=max(maxDiff[2*pos].valMax,maxDiff[2*pos+1].valMax);
	}
}

void nouvProp(int pos,int debInter,int finInter,int valProp) {
	if (maxDiff[pos].deb>finInter or maxDiff[pos].fin<debInter) {
		pushFlag(pos);
		return;
	}
	if (maxDiff[pos].deb>=debInter and maxDiff[pos].fin<=finInter) {
		//cout<<pos<<" "<<debInter<<" "<<finInter<<" "<<valProp<<" : ";
		maxDiff[pos].minProp=min(maxDiff[pos].minProp,valProp);
		maxDiff[pos].maxProp=max(maxDiff[pos].maxProp,valProp);
		//cout<<maxDiff[pos].minProp<<" "<<maxDiff[pos].maxProp<<endl;
		pushFlag(pos);
		return;
	}
	pushFlag(pos);
	nouvProp(2*pos,debInter,finInter,valProp);
	nouvProp(2*pos+1,debInter,finInter,valProp);
	maxDiff[pos].maxi=max(maxDiff[pos].maxi,max(maxDiff[2*pos].maxi,maxDiff[2*pos+1].maxi));
}

int calcMax(int pos,int debInter,int finInter) {
	pushFlag(pos);
	if (maxDiff[pos].deb>finInter or maxDiff[pos].fin<debInter) {
		return -1;
	}
	if (maxDiff[pos].deb>=debInter and maxDiff[pos].fin<=finInter) {
		return maxDiff[pos].maxi;
	}
	return max(calcMax(2*pos,debInter,finInter),calcMax(2*pos+1,debInter,finInter));
}

void afficher() {
	cout<<endl;
	for (int pos=1;pos<=100;pos++) {
		if (maxDiff[pos].deb>0) {
			cout<<pos<<" : "<<maxDiff[pos].deb<<" "<<maxDiff[pos].fin<<" "<<maxDiff[pos].valMin<<" "<<maxDiff[pos].valMax<<" "
				<<maxDiff[pos].minProp<<" "<<maxDiff[pos].maxProp<<" "<<maxDiff[pos].maxi<<endl;
		}
	}
	cout<<endl;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>taille;
	for (ll i=1;i<=taille;i++) {
		cin>>ant[i].hauteur>>ant[i].minDist>>ant[i].maxDist;
	}
	prepa(1,1,taille);
	cin>>nbReq;
	for (int i=0;i<nbReq;i++) {
		cin>>debReq>>finReq;
		reqFin[finReq].push_back({debReq,i});
	}
	for (ll i=1;i<=taille;i++) {
		for (ll j:ajout[i]) {
			modifSommet(1,j,1);
		}
		//afficher();
		if (ant[i].minDist<i) {
			//cout<<i<<" : "<<max((int)1,i-ant[i].maxDist)<<" "<<i-ant[i].minDist<<" "<<ant[i].hauteur<<endl;
			nouvProp(1,max((int)1,i-ant[i].maxDist),i-ant[i].minDist,ant[i].hauteur);
		}
		//afficher();
		if (i+ant[i].minDist<=taille) {
			ajout[i+ant[i].minDist].push_back(i);
		}
		if (i+ant[i].maxDist<=taille) {
			suppre[i+ant[i].maxDist].push_back(i);
		}
		for (auto k:reqFin[i]) {
			rep[k.second]=calcMax(1,k.first,i);
		}
		for (ll j:suppre[i]) {
			modifSommet(1,j,0);
		}
	}
	for (int i=0;i<nbReq;i++) {
		cout<<rep[i]<<"\n";
	}
	return 0;
}

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