oj.uz

Submission #433772

# Submission time Handle Problem Language Result Execution time Memory
433772 2021-06-20T10:37:32 Z JeanBombeur Street Lamps (APIO19_street_lamps) C++17
0 / 100
 949 ms 380096 KB 
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

//   <|°_°|>

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

struct node {
	int left, right, val = 1;
	void Print() {
		printf("%d %d %d\n", left, right, val);
	}
};

int State[MAX_LAMPES];

char Mot[MAX_LAMPES];

node Tree[TAILLE_ARBRE * 30];
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 (noeud < 0)
		return 1;
	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]);
	}
	for (int i = nbLampes; i < TAILLE_ARBRE; i ++)
	{
		Push(0, 0, TAILLE_ARBRE, i, 1);
	}
	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:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d %d", &nbLampes, &nbRequetes);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%s", Mot);
      |  ~~~~~^~~~~~~~~~~
street_lamps.cpp: In function 'void Solve()':
street_lamps.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%s %d", Mot, &a);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:92:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |    scanf("%d", &b);
      |    ~~~~~^~~~~~~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 184900 KB Output is correct
2 Correct 259 ms 185040 KB Output is correct
3 Correct 263 ms 184972 KB Output is correct
4 Correct 291 ms 184972 KB Output is correct
5 Runtime error 830 ms 380096 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 278 ms 184972 KB Output is correct
2 Incorrect 273 ms 185060 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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