oj.uz

Submission #1114943

# Submission time Handle Problem Language Result Execution time Memory
1114943 2024-11-19T20:16:35 Z AdamGS Fire (JOI20_ho_t5) C++17
7 / 100
 1000 ms 10568 KB 
#include <iostream>

using namespace std;

const int MAXN = 200001;

int n, q;

int drzewo_przedzialowe[(1 << 19) + 2];

int stala;

int val[MAXN];

int find_stala() {
	int x = 1;
	while (n > x) {
		x *= 2;
	}
	x--;
	return x;
}

void stworz_drzewo() {
	for (int i = 1; n >= i; i++) {
		drzewo_przedzialowe[i + stala] = val[i];
	}
	for (int i = stala; i > 0; i--) {
		drzewo_przedzialowe[i] = max(drzewo_przedzialowe[i << 1], drzewo_przedzialowe[(i << 1) + 1]);
	}	
}

int min_na_przedziale(int l, int r) {
	if (l == r) {
		return drzewo_przedzialowe[l];
	}
	int wynik = max(drzewo_przedzialowe[r], drzewo_przedzialowe[l]);
	if (l == (r - 1)) {
		return wynik;
	}
	while (r > (l + 1)) {
		if (l%2 == 0) {
			wynik = max(wynik, drzewo_przedzialowe[l + 1]);
		}
		if (r%2 == 1) {
			wynik = max(wynik, drzewo_przedzialowe[r - 1]);
		}
		r /= 2;
		l /= 2;
	}
	return wynik;
}

void poj() {
	int t, l, r;
	cin >> t >> l >> r;
	int suma = 0;
	int start;
	for (int i = l; r >= i; i++) {
		start = max((i - t), 1);
		suma += min_na_przedziale(start + stala, i + stala);
	}
	cout << suma << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> q;
	
	for (int i = 1; n >= i; i++) {
		cin >> val[i];
	}
	
	stala = find_stala();
	stworz_drzewo();
	
	for (int i = 0; q > i; i++) {
		poj();
	}
	return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Execution timed out 1034 ms 3936 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 109 ms 8264 KB Output is correct
3 Correct 82 ms 10400 KB Output is correct
4 Correct 83 ms 10568 KB Output is correct
5 Correct 81 ms 10312 KB Output is correct
6 Correct 81 ms 10320 KB Output is correct
7 Correct 81 ms 10396 KB Output is correct
8 Correct 83 ms 10556 KB Output is correct
9 Correct 81 ms 10324 KB Output is correct
10 Correct 80 ms 10312 KB Output is correct
11 Correct 83 ms 10568 KB Output is correct
12 Correct 80 ms 10424 KB Output is correct
13 Correct 89 ms 10540 KB Output is correct
14 Correct 88 ms 10312 KB Output is correct
15 Correct 83 ms 10568 KB Output is correct
16 Correct 80 ms 10240 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 3408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

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