oj.uz

Submission #1096204

# Submission time Handle Problem Language Result Execution time Memory
1096204 2024-10-04T05:39:22 Z stdfloat Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1231 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
#define sz(v)  (int)(v).size()
#define all(v) (v).begin(), v.end()
 
int mx, ch, md;

vector<int> a, st, vis;

vector<vector<int>> v;
 
void bld(int nd, int l, int r) {
	if (l == r) {
		vis[nd] = 0; st[nd] = a[l]; v[nd] = {a[l]};
		return;
	}
 
	ch = (nd << 1) + 1; md = l + r >> 1;
	bld(ch, l, md); bld(ch + 1, md + 1, r);
 
	st[nd] = max(st[ch], st[ch + 1]);
 
	v[nd].assign(sz(v[ch]) + sz(v[ch + 1]), 0);
	merge(all(v[ch]), all(v[ch + 1]), v[nd].begin());
	
	int mx = 0;
	for (int i = l; i <= r; i++) {
		if (mx > a[i]) vis[nd] = max(vis[nd], mx + a[i]);
		else mx = a[i];
	}
}
 
bool fnd(int nd, int l, int r, int x, int y, int k) {
	if (r < x || y < l) return true;
 
	if (x <= l && r <= y) {
		bool tr = (max(vis[nd], (mx > v[nd][0] ? mx + *--lower_bound(all(v[nd]), mx) : 0)) <= k);
		mx = max(mx, st[nd]);
		return tr;
	}
 
	ch = (nd << 1) + 1; md = l + r >> 1;
	return (!fnd(ch, l, md, x, y, k) || !fnd(ch + 1, md + 1, r, x, y, k) ? false : true);
}
 
int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
 
	int n, q;
	cin >> n >> q;
 
	a.assign(n, 0);
	for (auto &i : a)
		cin >> i;
 
	v.assign(n << 2, {});
	st = vis = vector<int>(n << 2);
	bld(0, 0, n - 1);
 
	while (q--) {
		int l, r, k;
		cin >> l >> r >> k; l--; r--;
 
		mx = 0;
		cout << fnd(0, 0, n - 1, l, r, k) << endl;
	}
}

Compilation message

sortbooks.cpp: In function 'void bld(int, int, int)':
sortbooks.cpp:21:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |  ch = (nd << 1) + 1; md = l + r >> 1;
      |                           ~~^~~
sortbooks.cpp: In function 'bool fnd(int, int, int, int, int, int)':
sortbooks.cpp:45:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |  ch = (nd << 1) + 1; md = l + r >> 1;
      |                           ~~^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1231 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 27224 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -