oj.uz

Submission #433715

# Submission time Handle Problem Language Result Execution time Memory
433715 2021-06-20T09:53:28 Z JeanBombeur Street Lamps (APIO19_street_lamps) C++17
0 / 100
 644 ms 146396 KB 
#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 = 0;

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

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.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70652 KB Output is correct
2 Correct 35 ms 70732 KB Output is correct
3 Correct 35 ms 70764 KB Output is correct
4 Correct 35 ms 70668 KB Output is correct
5 Runtime error 221 ms 146396 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 70640 KB Output is correct
2 Incorrect 36 ms 70740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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