oj.uz

Submission #535789

# Submission time Handle Problem Language Result Execution time Memory
535789 2022-03-11T08:29:24 Z abc864197532 Fire (JOI20_ho_t5) C++17
6 / 100
 116 ms 12100 KB 
 #include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
	cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
	for (; l != r; ++l)
		cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(x...) abc("[" + string(#x) + "]", x)
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define test(x...) void(0)
#define owo ios::sync_with_stdio(false), cin.tie(0)
#endif

int main () {
	owo;
	int n, q;
	cin >> n >> q;
	vector <int> a(n);
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	vector <int> mx(n);
	int t, l, r;
	cin >> t >> l >> r, q--, --l;
	deque <int> dq;
	for (int i = 0; i < n; ++i) {
		if (!dq.empty() && i - dq.front() == t + 1)
			dq.pop_front();
		while (!dq.empty() && a[dq.back()] <= a[i])
			dq.pop_back();
		dq.push_back(i);
		mx[i] = a[dq.front()];
	}
	vector <lli> pre(n + 1);
	for (int i = 0; i < n; ++i)
		pre[i + 1] = pre[i] + mx[i];
	cout << pre[r] - pre[l] << '\n';
	while (q--) {
		cin >> t >> l >> r, --l;
		cout << pre[r] - pre[l] << '\n';
	}
}

Subtask #1
0 / 1.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 98 ms 11868 KB Output is correct
3 Correct 92 ms 11852 KB Output is correct
4 Correct 116 ms 11884 KB Output is correct
5 Correct 91 ms 12032 KB Output is correct
6 Correct 106 ms 11704 KB Output is correct
7 Correct 106 ms 11944 KB Output is correct
8 Correct 110 ms 11952 KB Output is correct
9 Correct 115 ms 11904 KB Output is correct
10 Correct 108 ms 11948 KB Output is correct
11 Correct 116 ms 12100 KB Output is correct
12 Correct 91 ms 11800 KB Output is correct
13 Correct 102 ms 11852 KB Output is correct
14 Correct 98 ms 11708 KB Output is correct
15 Correct 101 ms 11840 KB Output is correct
16 Correct 110 ms 11688 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

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