Submission #433902

#	Time	Username	Problem	Language	Result	Execution time	Memory
433902		JeanBombeur	Bridges (APIO19_bridges)	C++17	16 / 100	192 ms	1204 KiB

bridges

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

//   <|°_°|>

const int INFINI = (1000 * 1000 * 1000);
const int MAX_NOEUDS = (100 * 1000);
const int TAILLE_ARBRE = (1 << 16);

int Tree[2 * TAILLE_ARBRE];

int nbNoeuds, nbAretes, nbRequetes;

void Set(int id, int val) {	
	id += TAILLE_ARBRE;
	Tree[id] = val;
	for (int i = id / 2; i > 0; i /= 2)
	{
		Tree[i] = min(Tree[2 * i], Tree[2 * i + 1]);
	}
	return;
}

int GetMin(int gauche, int droite) {
	int ans = INFINI;
	if (gauche > droite)
		return ans;
	if (gauche & 1)
		ans = min(ans, Tree[gauche ++]);
	if (!(droite & 1))
		ans = min(ans, Tree[droite --]);
	return min(ans, GetMin(gauche / 2, droite / 2));
}

void Read() {
	scanf("%d %d", &nbNoeuds, &nbAretes);
	for (int i = 0; i < nbAretes; i ++)
	{
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		Tree[i + TAILLE_ARBRE] = c;
	}
	for (int i = TAILLE_ARBRE - 1; i > 0; i --)
	{
		Tree[i] = min(Tree[2 * i], Tree[2 * i + 1]);
	}
	return;
}

void Solve() {
	scanf("%d", &nbRequetes);
	for (int i = 0; i < nbRequetes; i ++)
	{
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		b --;
		if (a == 1)
			Set(b, c);
		else
		{
			int ans = 1;
			int pos = b - 1;
			for (int j = (1 << 15); j > 0; j /= 2)
			{
				if (pos + j < nbNoeuds && GetMin(pos + 1 + TAILLE_ARBRE, pos + j + TAILLE_ARBRE) >= c)
					pos += j;
			}
			ans += pos - b + 1;
			pos = b;
			for (int j = (1 << 15); j > 0; j /= 2)
			{
				if (pos - j >= 0 && GetMin(pos - j + TAILLE_ARBRE, pos - 1 + TAILLE_ARBRE) >= c)
					pos -= j;
			}
			ans += b - pos;
			printf("%d\n", ans);
		}
	}
	return;
}

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

Compilation message (stderr)

bridges.cpp: In function 'void Read()':
bridges.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d %d", &nbNoeuds, &nbAretes);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d %d %d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'void Solve()':
bridges.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%d", &nbRequetes);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d %d %d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27