Submission #1114943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114943		AdamGS	Fire (JOI20_ho_t5)	C++17	7 / 100	1054 ms	10568 KiB

ho_t5

#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
• Subtask 2: 0 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80