oj.uz

Submission #500428

# Submission time Handle Problem Language Result Execution time Memory
500428 2021-12-31T06:05:24 Z Mazaalai Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 2493 ms 262148 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII = pair <int, int>;
using VI = vector <int>;
using VVI = vector <VI>;
using VPI = vector <PII>;
struct Node {
	int max, max1, maxInv;
	Node() {
		max = max1 = -1;
		maxInv = -1;
	}
};
const int N = 1e6 + 5;
const int M = 4 * N;
int n, m;
VPI addNum;
int nums[N], queries[N], K[N];
Node node[M];
void build(int l, int r, int head) {
	if (l == r) {
		node[head].max = nums[l];
		return;
	}
	int mid = (l+r)>>1;
	build(l, mid, head*2+1);
	build(mid+1, r, head*2+2);
	node[head].max = max(node[head*2+1].max, node[head*2+2].max);
	int curMax = nums[l];
	for (int i = l+1; i <= r; i++) {
		if (nums[i] >= curMax) curMax = nums[i];
		else node[head].maxInv = max(node[head].maxInv, curMax+nums[i]);
	}
}
void update(int l, int r, int id, int val, int head) {
	if (l == r) {
		node[head].max1 = val;
		return;
	}
	int mid = (l+r)>>1;
	if (id <= mid) update(l, mid, id, val, head*2+1);
	else update(mid+1, r, id, val, head*2+2);
	node[head].max1 = max(node[head*2+1].max1, node[head*2+2].max1);
}
int query(int l, int r, int L, int R, int head) {
	if (l > R || L > r) return -1;
	if (L <= l && r <= R) 
		return node[head].max1;
	
	int mid = (l+r)>>1;
	return max(
		query(l, mid, L, R, head*2+1),
		query(mid+1, r, L, R, head*2+2)
	);
}
set <VI> allCheck;// lMax, id, mid, r, head;
int dfs(int l, int r, int L, int R, int id, int head) { // return insideMax;
	if (L <= l && r <= R) {
		queries[id] = max(queries[id], node[head].maxInv);
		return node[head].max;
	}
	int mid = (l+r)>>1;
	if (R <= mid) return dfs(l, mid, L, R, id, head*2+1);
	if (mid+1 <= L) return dfs(mid+1, r, L, R, id, head*2+2);
	int lMax = dfs(l, mid, L, R, id, head*2+1);
	int rMax = dfs(mid+1, r, L, R, id, head*2+2);
	allCheck.insert({lMax, id, mid+1, r, L, R, head*2+2});
	return max(lMax, rMax);
}
signed main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> nums[i];
		addNum.pb({nums[i], i});
	}
	build(1, n, 0);
	sort(ALL(addNum));
	memset(queries, -1, sizeof(queries));
	for (int i = 1; i <= m; i++) {
		int l, r, k; cin >> l >> r >> k;
		K[i] = k;
		dfs(1, n, l, r, i, 0);
	}
	int addId = 0, lMax, id, L, R, mid, r, head;
	while(!allCheck.empty()) {
		auto it = allCheck.begin();
		VI tmp = *it;
		allCheck.erase(it);
		lMax = tmp[0];
		id = tmp[1];
		mid = tmp[2];
		r = tmp[3];
		L = tmp[4];
		R = tmp[5];
		head = tmp[6];
		while (addId < addNum.size() && lMax > addNum[addId].ff) {
			int num, I;
			tie(num, I) = addNum[addId++];
			update(1, n, I, num, 0);
		}
		int rMax = query(mid, r, L, R, head);
		int cur = (rMax == -1 ? -1 : lMax+rMax);
		queries[id] = max(queries[id], cur);
		// cout << "UPdate: " << id << ' ' << cur << ' ' << lMax << ' ' << rMax << ' ' << mid << ' ' << r << '\n';
	}
	// for (int i = 1; i <= m; i++)
	// 	cout << queries[i] << ' ' << K[i] << '\n';
	for (int i = 1; i <= m; i++)
		cout << (queries[i] <= K[i] ? 1 : 0) << '\n';
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:102:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   while (addId < addNum.size() && lMax > addNum[addId].ff) {
      |          ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51148 KB Output is correct
2 Correct 21 ms 51088 KB Output is correct
3 Correct 23 ms 51368 KB Output is correct
4 Correct 23 ms 51236 KB Output is correct
5 Correct 22 ms 51140 KB Output is correct
6 Correct 23 ms 51532 KB Output is correct
7 Correct 25 ms 51444 KB Output is correct
8 Correct 23 ms 51404 KB Output is correct
9 Correct 23 ms 51252 KB Output is correct
10 Correct 27 ms 51368 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51148 KB Output is correct
2 Correct 21 ms 51088 KB Output is correct
3 Correct 23 ms 51368 KB Output is correct
4 Correct 23 ms 51236 KB Output is correct
5 Correct 22 ms 51140 KB Output is correct
6 Correct 23 ms 51532 KB Output is correct
7 Correct 25 ms 51444 KB Output is correct
8 Correct 23 ms 51404 KB Output is correct
9 Correct 23 ms 51252 KB Output is correct
10 Correct 27 ms 51368 KB Output is correct
11 Correct 37 ms 53728 KB Output is correct
12 Correct 38 ms 54004 KB Output is correct
13 Correct 41 ms 54368 KB Output is correct
14 Correct 53 ms 56436 KB Output is correct
15 Correct 53 ms 56468 KB Output is correct
16 Correct 48 ms 55660 KB Output is correct
17 Correct 40 ms 53572 KB Output is correct
18 Correct 39 ms 54952 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1273 ms 194372 KB Output is correct
2 Correct 1480 ms 241880 KB Output is correct
3 Correct 1501 ms 218644 KB Output is correct
4 Correct 1428 ms 208496 KB Output is correct
5 Correct 1288 ms 196332 KB Output is correct
6 Runtime error 787 ms 262148 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51148 KB Output is correct
2 Correct 21 ms 51088 KB Output is correct
3 Correct 23 ms 51368 KB Output is correct
4 Correct 23 ms 51236 KB Output is correct
5 Correct 22 ms 51140 KB Output is correct
6 Correct 23 ms 51532 KB Output is correct
7 Correct 25 ms 51444 KB Output is correct
8 Correct 23 ms 51404 KB Output is correct
9 Correct 23 ms 51252 KB Output is correct
10 Correct 27 ms 51368 KB Output is correct
11 Correct 37 ms 53728 KB Output is correct
12 Correct 38 ms 54004 KB Output is correct
13 Correct 41 ms 54368 KB Output is correct
14 Correct 53 ms 56436 KB Output is correct
15 Correct 53 ms 56468 KB Output is correct
16 Correct 48 ms 55660 KB Output is correct
17 Correct 40 ms 53572 KB Output is correct
18 Correct 39 ms 54952 KB Output is correct
19 Runtime error 2153 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51148 KB Output is correct
2 Correct 21 ms 51088 KB Output is correct
3 Correct 23 ms 51368 KB Output is correct
4 Correct 23 ms 51236 KB Output is correct
5 Correct 22 ms 51140 KB Output is correct
6 Correct 23 ms 51532 KB Output is correct
7 Correct 25 ms 51444 KB Output is correct
8 Correct 23 ms 51404 KB Output is correct
9 Correct 23 ms 51252 KB Output is correct
10 Correct 27 ms 51368 KB Output is correct
11 Correct 37 ms 53728 KB Output is correct
12 Correct 38 ms 54004 KB Output is correct
13 Correct 41 ms 54368 KB Output is correct
14 Correct 53 ms 56436 KB Output is correct
15 Correct 53 ms 56468 KB Output is correct
16 Correct 48 ms 55660 KB Output is correct
17 Correct 40 ms 53572 KB Output is correct
18 Correct 39 ms 54952 KB Output is correct
19 Runtime error 2493 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -