oj.uz

Submission #433620

# Submission time Handle Problem Language Result Execution time Memory
433620 2021-06-20T08:38:15 Z oscar1f Street Lamps (APIO19_street_lamps) C++17
20 / 100
 733 ms 11420 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 337 ms 2948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 4 ms 2352 KB Output is correct
3 Correct 4 ms 2380 KB Output is correct
4 Correct 4 ms 2380 KB Output is correct
5 Correct 106 ms 7740 KB Output is correct
6 Correct 341 ms 8388 KB Output is correct
7 Correct 533 ms 9152 KB Output is correct
8 Correct 721 ms 11360 KB Output is correct
9 Correct 483 ms 5984 KB Output is correct
10 Correct 560 ms 6232 KB Output is correct
11 Correct 523 ms 6656 KB Output is correct
12 Correct 733 ms 10048 KB Output is correct
13 Correct 704 ms 11420 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2252 KB Output is correct
2 Incorrect 4 ms 2380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2252 KB Output isn't correct
2 Halted 0 ms 0 KB -