oj.uz

Submission #500430

# Submission time Handle Problem Language Result Execution time Memory
500430 2021-12-31T06:06:54 Z Mazaalai Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 2448 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 24 ms 51080 KB Output is correct
2 Correct 22 ms 51096 KB Output is correct
3 Correct 23 ms 51260 KB Output is correct
4 Correct 23 ms 51176 KB Output is correct
5 Correct 23 ms 51184 KB Output is correct
6 Correct 24 ms 51436 KB Output is correct
7 Correct 24 ms 51404 KB Output is correct
8 Correct 24 ms 51388 KB Output is correct
9 Correct 23 ms 51276 KB Output is correct
10 Correct 24 ms 51408 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51080 KB Output is correct
2 Correct 22 ms 51096 KB Output is correct
3 Correct 23 ms 51260 KB Output is correct
4 Correct 23 ms 51176 KB Output is correct
5 Correct 23 ms 51184 KB Output is correct
6 Correct 24 ms 51436 KB Output is correct
7 Correct 24 ms 51404 KB Output is correct
8 Correct 24 ms 51388 KB Output is correct
9 Correct 23 ms 51276 KB Output is correct
10 Correct 24 ms 51408 KB Output is correct
11 Correct 38 ms 53608 KB Output is correct
12 Correct 39 ms 53932 KB Output is correct
13 Correct 42 ms 54320 KB Output is correct
14 Correct 58 ms 56372 KB Output is correct
15 Correct 54 ms 56336 KB Output is correct
16 Correct 48 ms 55504 KB Output is correct
17 Correct 37 ms 53444 KB Output is correct
18 Correct 39 ms 54852 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2448 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 1282 ms 194616 KB Output is correct
2 Correct 1475 ms 239796 KB Output is correct
3 Correct 1502 ms 216808 KB Output is correct
4 Correct 1409 ms 206548 KB Output is correct
5 Correct 1339 ms 194488 KB Output is correct
6 Runtime error 764 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 24 ms 51080 KB Output is correct
2 Correct 22 ms 51096 KB Output is correct
3 Correct 23 ms 51260 KB Output is correct
4 Correct 23 ms 51176 KB Output is correct
5 Correct 23 ms 51184 KB Output is correct
6 Correct 24 ms 51436 KB Output is correct
7 Correct 24 ms 51404 KB Output is correct
8 Correct 24 ms 51388 KB Output is correct
9 Correct 23 ms 51276 KB Output is correct
10 Correct 24 ms 51408 KB Output is correct
11 Correct 38 ms 53608 KB Output is correct
12 Correct 39 ms 53932 KB Output is correct
13 Correct 42 ms 54320 KB Output is correct
14 Correct 58 ms 56372 KB Output is correct
15 Correct 54 ms 56336 KB Output is correct
16 Correct 48 ms 55504 KB Output is correct
17 Correct 37 ms 53444 KB Output is correct
18 Correct 39 ms 54852 KB Output is correct
19 Runtime error 2145 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 24 ms 51080 KB Output is correct
2 Correct 22 ms 51096 KB Output is correct
3 Correct 23 ms 51260 KB Output is correct
4 Correct 23 ms 51176 KB Output is correct
5 Correct 23 ms 51184 KB Output is correct
6 Correct 24 ms 51436 KB Output is correct
7 Correct 24 ms 51404 KB Output is correct
8 Correct 24 ms 51388 KB Output is correct
9 Correct 23 ms 51276 KB Output is correct
10 Correct 24 ms 51408 KB Output is correct
11 Correct 38 ms 53608 KB Output is correct
12 Correct 39 ms 53932 KB Output is correct
13 Correct 42 ms 54320 KB Output is correct
14 Correct 58 ms 56372 KB Output is correct
15 Correct 54 ms 56336 KB Output is correct
16 Correct 48 ms 55504 KB Output is correct
17 Correct 37 ms 53444 KB Output is correct
18 Correct 39 ms 54852 KB Output is correct
19 Runtime error 2448 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -