oj.uz

답안 #500528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500528 2021-12-31T09:51:38 Z Mazaalai Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 2857 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 ll = long long;
using PII = pair <int, int>;
using VI = vector <int>;
using VVI = vector <VI>;
using VPI = vector <PII>;
struct Node {
	int max, maxInv;
	Node() {
		max = -1;
		maxInv = -1;
	}
};
const int N = 2e5 + 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].max = 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].max = max(node[head*2+1].max, node[head*2+2].max);
}
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].max;
	
	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, l, r;
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);
	// lRange = max(mid+1, L), rRange = min(r, R);
	allCheck.insert({lMax, id, max(mid+1, L), min(r, R)});
	lMax = max(lMax, dfs(mid+1, r, L, R, id, head*2+2));
	return lMax;
}
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));
	int l, r;
	for (int i = 1; i <= m; i++) {
		cin >> l >> r >> K[i];
		dfs(1, n, l, r, i, 0);
	}
	for (int i = 0; i < M; i++) node[i].max = -1;
	int addId = 0, lMax, id, L, R, mid, head;
	VI tmp;
	while(!allCheck.empty()) {
		auto it = allCheck.begin();
		tmp = *it;
		allCheck.erase(it);
		lMax = tmp[0];
		id = tmp[1];
		l = tmp[2];
		r = tmp[3];
		while (addId < addNum.size() && lMax > addNum[addId].ff) {
			int num, I;
			tie(num, I) = addNum[addId++];
			update(1, n, I, num, 0);
		}
		if (lMax * 2 - 1 <= queries[id]) continue;
		int cur = query(1, n, l, r, 0);
		cur = (cur == -1 ? -1 : lMax+cur);
		queries[id] = max(queries[id], cur);
	}
	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:103: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]
  103 |   while (addId < addNum.size() && lMax > addNum[addId].ff) {
      |          ~~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:93:27: warning: unused variable 'L' [-Wunused-variable]
   93 |  int addId = 0, lMax, id, L, R, mid, head;
      |                           ^
sortbooks.cpp:93:30: warning: unused variable 'R' [-Wunused-variable]
   93 |  int addId = 0, lMax, id, L, R, mid, head;
      |                              ^
sortbooks.cpp:93:33: warning: unused variable 'mid' [-Wunused-variable]
   93 |  int addId = 0, lMax, id, L, R, mid, head;
      |                                 ^~~
sortbooks.cpp:93:38: warning: unused variable 'head' [-Wunused-variable]
   93 |  int addId = 0, lMax, id, L, R, mid, head;
      |                                      ^~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7324 KB Output is correct
3 Correct 5 ms 7500 KB Output is correct
4 Correct 5 ms 7336 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 6 ms 7600 KB Output is correct
7 Correct 6 ms 7628 KB Output is correct
8 Correct 6 ms 7596 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 5 ms 7500 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7324 KB Output is correct
3 Correct 5 ms 7500 KB Output is correct
4 Correct 5 ms 7336 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 6 ms 7600 KB Output is correct
7 Correct 6 ms 7628 KB Output is correct
8 Correct 6 ms 7596 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 5 ms 7500 KB Output is correct
11 Correct 17 ms 9548 KB Output is correct
12 Correct 20 ms 9768 KB Output is correct
13 Correct 22 ms 10136 KB Output is correct
14 Correct 32 ms 11880 KB Output is correct
15 Correct 32 ms 11936 KB Output is correct
16 Correct 28 ms 11204 KB Output is correct
17 Correct 19 ms 9384 KB Output is correct
18 Correct 22 ms 10548 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 84 ms 18432 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1071 ms 132408 KB Output is correct
2 Correct 1201 ms 171140 KB Output is correct
3 Correct 1488 ms 151404 KB Output is correct
4 Correct 1537 ms 142596 KB Output is correct
5 Correct 1302 ms 132208 KB Output is correct
6 Correct 1562 ms 205304 KB Output is correct
7 Correct 1556 ms 205340 KB Output is correct
8 Correct 562 ms 100340 KB Output is correct
9 Correct 255 ms 33988 KB Output is correct
10 Correct 533 ms 100352 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7324 KB Output is correct
3 Correct 5 ms 7500 KB Output is correct
4 Correct 5 ms 7336 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 6 ms 7600 KB Output is correct
7 Correct 6 ms 7628 KB Output is correct
8 Correct 6 ms 7596 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 5 ms 7500 KB Output is correct
11 Correct 17 ms 9548 KB Output is correct
12 Correct 20 ms 9768 KB Output is correct
13 Correct 22 ms 10136 KB Output is correct
14 Correct 32 ms 11880 KB Output is correct
15 Correct 32 ms 11936 KB Output is correct
16 Correct 28 ms 11204 KB Output is correct
17 Correct 19 ms 9384 KB Output is correct
18 Correct 22 ms 10548 KB Output is correct
19 Runtime error 2857 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7324 KB Output is correct
3 Correct 5 ms 7500 KB Output is correct
4 Correct 5 ms 7336 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 6 ms 7600 KB Output is correct
7 Correct 6 ms 7628 KB Output is correct
8 Correct 6 ms 7596 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 5 ms 7500 KB Output is correct
11 Correct 17 ms 9548 KB Output is correct
12 Correct 20 ms 9768 KB Output is correct
13 Correct 22 ms 10136 KB Output is correct
14 Correct 32 ms 11880 KB Output is correct
15 Correct 32 ms 11936 KB Output is correct
16 Correct 28 ms 11204 KB Output is correct
17 Correct 19 ms 9384 KB Output is correct
18 Correct 22 ms 10548 KB Output is correct
19 Runtime error 84 ms 18432 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -