oj.uz

Submission #500440

# Submission time Handle Problem Language Result Execution time Memory
500440 2021-12-31T06:16:44 Z Mazaalai Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 2555 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:90:6: warning: unused variable 'addId' [-Wunused-variable]
   90 |  int addId = 0, lMax, id, L, R, mid, r, head;
      |      ^~~~~
sortbooks.cpp:90:17: warning: unused variable 'lMax' [-Wunused-variable]
   90 |  int addId = 0, lMax, id, L, R, mid, r, head;
      |                 ^~~~
sortbooks.cpp:90:23: warning: unused variable 'id' [-Wunused-variable]
   90 |  int addId = 0, lMax, id, L, R, mid, r, head;
      |                       ^~
sortbooks.cpp:90:27: warning: unused variable 'L' [-Wunused-variable]
   90 |  int addId = 0, lMax, id, L, R, mid, r, head;
      |                           ^
sortbooks.cpp:90:30: warning: unused variable 'R' [-Wunused-variable]
   90 |  int addId = 0, lMax, id, L, R, mid, r, head;
      |                              ^
sortbooks.cpp:90:33: warning: unused variable 'mid' [-Wunused-variable]
   90 |  int addId = 0, lMax, id, L, R, mid, r, head;
      |                                 ^~~
sortbooks.cpp:90:38: warning: unused variable 'r' [-Wunused-variable]
   90 |  int addId = 0, lMax, id, L, R, mid, r, head;
      |                                      ^
sortbooks.cpp:90:41: warning: unused variable 'head' [-Wunused-variable]
   90 |  int addId = 0, lMax, id, L, R, mid, r, head;
      |                                         ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51088 KB Output is correct
2 Correct 24 ms 51084 KB Output is correct
3 Incorrect 23 ms 51276 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51088 KB Output is correct
2 Correct 24 ms 51084 KB Output is correct
3 Incorrect 23 ms 51276 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2555 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 Incorrect 974 ms 194412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51088 KB Output is correct
2 Correct 24 ms 51084 KB Output is correct
3 Incorrect 23 ms 51276 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51088 KB Output is correct
2 Correct 24 ms 51084 KB Output is correct
3 Incorrect 23 ms 51276 KB Output isn't correct
4 Halted 0 ms 0 KB -