Submission #433729

#	Time	Username	Problem	Language	Result	Execution time	Memory
433729		JeanBombeur	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	578 ms	146296 KiB

street_lamps

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

//   <|°_°|>

const int MAX_LAMPES = (300 * 1000);
const int TAILLE_ARBRE = (1 << 19);

struct node {
	int left, right, val = 1;
};

int State[MAX_LAMPES];

char Mot[MAX_LAMPES + 1];

node Tree[MAX_LAMPES * 20];
int sz = 1;

int Racine[MAX_LAMPES];

int nbLampes, nbRequetes;

int Copy(int a, int &b) {
	Tree[sz] = Tree[a];
	return b = sz ++;
}

int MakeRoot(int id) {
	return Copy(Racine[id - 1], Racine[id]);
}

void Push(int noeud, int gauche, int droite, int target, int add) {
	if (droite - gauche == 1)
	{
		Tree[noeud].val = add;
		return;
	}
	int mid = (gauche + droite) / 2;
	if (target < mid)
		Push(Copy(Tree[noeud].left, Tree[noeud].left), gauche, mid, target, add);
	else
		Push(Copy(Tree[noeud].right, Tree[noeud].right), mid, droite, target, add);
	Tree[noeud].val = min(Tree[Tree[noeud].left].val, Tree[Tree[noeud].right].val);
	return;
}

int GetMin(int noeud, int gauche, int droite, int inf, int sup) {
	if (gauche >= sup || droite <= inf)
		return 1;
	if (gauche >= inf && droite <= sup)
		return Tree[noeud].val;
	int mid = (gauche + droite) / 2;
	return min(GetMin(Tree[noeud].left, gauche, mid, inf, sup), GetMin(Tree[noeud].right, mid, droite, inf, sup));
}

void Read() {
	scanf("%d %d", &nbLampes, &nbRequetes);
	scanf("%s", Mot);
	for (int i = 0; i < nbLampes; i ++)
	{
		State[i] = Mot[i] == '1';
		Push(0, 0, TAILLE_ARBRE, i, State[i]);
	}
	return;
}

void Solve() {
	for (int i = 1; i <= nbRequetes; i ++)
	{
		Racine[i] = MakeRoot(i);
		int a, b;
		scanf("%s %d", Mot, &a);
		a --;
		if (Mot[0] == 't')
		{
			Push(Racine[i], 0, TAILLE_ARBRE, a, 1);
		}
		else
		{
			scanf("%d", &b);
			b --;
			int ans = -1;
			for (int j = (1 << 18); j > 0; j /= 2)
			{
				if (ans + j < i && GetMin(Racine[ans + j], 0, TAILLE_ARBRE, a, b) == 0)
					ans += j;
			}
			printf("%d\n", i - (++ ans));
		}
	}
	return;
}

int main() {
	Read();
	Solve();
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void Read()':
street_lamps.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d %d", &nbLampes, &nbRequetes);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%s", Mot);
      |  ~~~~~^~~~~~~~~~~
street_lamps.cpp: In function 'void Solve()':
street_lamps.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   scanf("%s %d", Mot, &a);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:83:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |    scanf("%d", &b);
      |    ~~~~~^~~~~~~~~~

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