oj.uz

답안 #433902

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433902 2021-06-20T12:01:47 Z JeanBombeur 다리 (APIO19_bridges) C++17
16 / 100
 192 ms 1204 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 732 KB Output is correct
2 Correct 135 ms 864 KB Output is correct
3 Correct 132 ms 980 KB Output is correct
4 Correct 133 ms 744 KB Output is correct
5 Correct 151 ms 804 KB Output is correct
6 Correct 129 ms 988 KB Output is correct
7 Correct 141 ms 1008 KB Output is correct
8 Correct 137 ms 992 KB Output is correct
9 Correct 45 ms 712 KB Output is correct
10 Correct 134 ms 836 KB Output is correct
11 Correct 121 ms 872 KB Output is correct
12 Correct 192 ms 1204 KB Output is correct
13 Correct 72 ms 768 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 151 ms 756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 24 ms 844 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 732 KB Output is correct
2 Correct 135 ms 864 KB Output is correct
3 Correct 132 ms 980 KB Output is correct
4 Correct 133 ms 744 KB Output is correct
5 Correct 151 ms 804 KB Output is correct
6 Correct 129 ms 988 KB Output is correct
7 Correct 141 ms 1008 KB Output is correct
8 Correct 137 ms 992 KB Output is correct
9 Correct 45 ms 712 KB Output is correct
10 Correct 134 ms 836 KB Output is correct
11 Correct 121 ms 872 KB Output is correct
12 Correct 192 ms 1204 KB Output is correct
13 Correct 72 ms 768 KB Output is correct
14 Incorrect 151 ms 756 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -