Submission #433620

#	Time	Username	Problem	Language	Result	Execution time	Memory
433620		oscar1f	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	733 ms	11420 KiB

street_lamps

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

const int INFINI=1000*1000*1000,DECA=(1<<19);
int nbLampe,nbReq,pos,nbTaxi,deb,fin,rep;
int arbreMax[2*DECA];
char carac;
string typeReq;

void maintien_max(int position) {
	if (position>0) {
		arbreMax[position]=max(arbreMax[2*position],arbreMax[2*position+1]);
		maintien_max(position/2);
	}
}

int calc_max(int debInter,int finInter) {
	if (debInter==finInter) {
		return arbreMax[debInter];
	}
	if (debInter%2==1) {
		return max(arbreMax[debInter],calc_max(debInter+1,finInter));
	}
	if (finInter%2==0) {
		return max(arbreMax[finInter],calc_max(debInter,finInter-1));
	}
	return calc_max(debInter/2,finInter/2);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin>>nbLampe>>nbReq;
	nbTaxi=nbLampe+1;
	for (int i=1;i<=nbLampe;i++) {
		cin>>carac;
		if (carac=='1') {
			arbreMax[DECA+i-1]=0;
		}
		else {
			arbreMax[DECA+i-1]=INFINI;
		}
	}
	for (int i=DECA-1;i>0;i--) {
		arbreMax[i]=max(arbreMax[2*i],arbreMax[2*i+1]);
	}
	for (int ireq=1;ireq<=nbReq;ireq++) {
		cin>>typeReq;
		if (typeReq=="toggle") {
			cin>>pos;
			arbreMax[DECA+pos-1]=ireq;
			maintien_max((DECA+pos-1)/2);
		}
		else {
			cin>>deb>>fin;
			rep=calc_max(DECA+deb-1,DECA+fin-2);
			if (rep==INFINI) {
				cout<<0<<endl;
			}
			else {
				cout<<ireq-rep<<endl;
			}
		}
	}
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20