oj.uz

Submission #433775

# Submission time Handle Problem Language Result Execution time Memory
433775 2021-06-20T10:39:03 Z JeanBombeur Street Lamps (APIO19_street_lamps) C++17
20 / 100
 2850 ms 251428 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 * 40];
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 288 ms 246468 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 248628 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 298 ms 246516 KB Output is correct
2 Correct 288 ms 246532 KB Output is correct
3 Correct 285 ms 246596 KB Output is correct
4 Correct 299 ms 246484 KB Output is correct
5 Correct 606 ms 249192 KB Output is correct
6 Correct 1080 ms 249376 KB Output is correct
7 Correct 1463 ms 249412 KB Output is correct
8 Correct 2839 ms 251428 KB Output is correct
9 Correct 1016 ms 248332 KB Output is correct
10 Correct 1070 ms 248328 KB Output is correct
11 Correct 1175 ms 248440 KB Output is correct
12 Correct 1900 ms 249752 KB Output is correct
13 Correct 2850 ms 251188 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 246528 KB Output is correct
2 Incorrect 290 ms 246656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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