이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 {
short int max, maxInv;
Node() {
max = -1;
maxInv = -1;
}
};
const int N = 2e5 + 5;
const int M = 4 * N;
int n, m;
VPI addNum;
short 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, 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);
allCheck.insert({lMax, id, mid+1, r, L, R, head*2+2});
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];
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);
}
if (lMax * 2 - 1 <= queries[id]) continue;
int cur = query(mid, r, L, R, head);
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';
}
컴파일 시 표준 에러 (stderr) 메시지
sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:37:65: error: no matching function for call to 'max(short int&, int)'
37 | else node[head].maxInv = max(node[head].maxInv, curMax+nums[i]);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from sortbooks.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
sortbooks.cpp:37:65: note: deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
37 | else node[head].maxInv = max(node[head].maxInv, curMax+nums[i]);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from sortbooks.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
sortbooks.cpp:37:65: note: deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
37 | else node[head].maxInv = max(node[head].maxInv, curMax+nums[i]);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from sortbooks.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
sortbooks.cpp:37:65: note: mismatched types 'std::initializer_list<_Tp>' and 'short int'
37 | else node[head].maxInv = max(node[head].maxInv, curMax+nums[i]);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from sortbooks.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
sortbooks.cpp:37:65: note: mismatched types 'std::initializer_list<_Tp>' and 'short int'
37 | else node[head].maxInv = max(node[head].maxInv, curMax+nums[i]);
| ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:105: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]
105 | while (addId < addNum.size() && lMax > addNum[addId].ff) {
| ~~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:113:37: error: no matching function for call to 'max(short int&, int&)'
113 | queries[id] = max(queries[id], cur);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from sortbooks.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
sortbooks.cpp:113:37: note: deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
113 | queries[id] = max(queries[id], cur);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from sortbooks.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
sortbooks.cpp:113:37: note: deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
113 | queries[id] = max(queries[id], cur);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from sortbooks.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
sortbooks.cpp:113:37: note: mismatched types 'std::initializer_list<_Tp>' and 'short int'
113 | queries[id] = max(queries[id], cur);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from sortbooks.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
sortbooks.cpp:113:37: note: mismatched types 'std::initializer_list<_Tp>' and 'short int'
113 | queries[id] = max(queries[id], cur);
| ^