이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, x, t[200005], ans = 0;
int sg[200005];
void build(int index, int l, int r) {
if (l == r) {
sg[index] = INT_MIN;
return;
}
int m = (l+r)/2;
build(index*2, l, m);
build(index*2+1, m+1, r);
sg[index] = max(sg[index*2], sg[index*2+1]);
}
int query(int index, int l, int r, int x, int y) {
if (x <= l and y >= r) return sg[index];
else if ((l < x and r < x) or (l > y and r > y)) return INT_MIN;
int m = (l+r)/2;
return max(query(index*2, l, m, x, y), query(index*2+1, m+1, r, x, y));
}
void update(int index, int l, int r, int pos, int val) {
if (pos < l or pos > r) return;
else if (l == r) {
sg[index] = val;
return;
}
int m = (l+r)/2;
if (pos <= m) {
update(index*2, l, m, pos, val);
} else update(index*2+1, m+1, r, pos, val);
sg[index] = max(sg[index*2], sg[index*2+1]);
}
void solve(int l, int r, int s) {
// cout << "loop : " << l << " " << r << " " << s << endl;
map<int, int> maks;
set<int, greater<int>> memo;
set<int>::iterator it;
vector<int> compress;
map<int, int> idx;
build(1, 0, n);
int cur;
for (int i = l; i <= r; i++) {
t[i] += s;
compress.push_back(t[i]);
}
for (int i = 0; i < compress.size(); i++) {
idx[compress[i]] = i;
}
stack<int> st;
int temp, temp2;
for (int i = 1; i <= n; i++) {
while (!st.empty()) {
if (t[i] <= st.top()) st.pop();
else break;
}
st.push(t[i]);
memo.insert(t[i]);
temp = st.size();
// update(1, 0, n, t[i])
temp2 = query(1, 0, n, idx[t[i]], idx[t[i]]);
if (temp > temp2) {
update(1, 0, n, idx[t[i]], temp);
}
// maks[t[i]] = max(maks[t[i]], temp);
// if (memo.size() > 1) {
// for (it = memo.begin(); it != memo.end(); it++) {
// if ((*it) == t[i]) break;
// }
// it++;
// if (it != memo.end()) {
// maks[t[i]] = max(maks[t[i]], maks[*it]+1);
// }
// }
// for (it = memo.begin(); it != memo.end(); it++) {
// if ((*it) < t[i]) {
// maks[t[i]] = max(maks[t[i]], maks[*it]+1);
// }
// }
update(1, 0, n, idx[t[i]], query(1, 0, n, 0, idx[t[i]]));
temp = query(1, 0, n, 0, idx[t[i]]);
// cout << i << " " << t[i] << " " << temp << endl;
ans = max(temp, ans);
}
for (int i = l; i <= r; i++) {
t[i] -= s;
}
}
signed main() {
cin >> n >> x;
for (int i = 1; i <= n; i++) cin >> t[i];
if (x == 0) {
solve(1, n, 0);
cout << ans << endl;
return 0;
}
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
for (int s = -x; s <= x; s++) {
solve(l, r, s);
}
}
}
cout << ans << endl;
}
컴파일 시 표준 에러 (stderr) 메시지
glo.cpp: In function 'void solve(long long int, long long int, long long int)':
glo.cpp:62:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int i = 0; i < compress.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
glo.cpp:56:7: warning: unused variable 'cur' [-Wunused-variable]
56 | int cur;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |