이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const ll LINF = ll(4e18) + ll(2e15);
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
static int LamyIsCute = []() {
EmiliaMyWife
return 48763;
}();
const int N = 3e5 + 25;
struct segtree {
int n, arr[N << 1], tag[N];
void init(int _n) { n = _n; }
void upd(int p, int v) {
arr[p] += v;
if(p < n)
tag[p] += v;
}
void pull(int p) {
for(; p > 1; p >>= 1)
arr[p >> 1] = max(arr[p], arr[p ^ 1]) + tag[p >> 1];
}
void edt(int l, int r, int v) {
int tl = l + n, tr = r + n - 1;
for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l & 1)
upd(l++, v);
if(r & 1)
upd(--r, v);
}
pull(tl);
pull(tr);
}
int que() { return arr[1]; }
} tree;
signed main() {
int n, d;
cin >> n >> d;
assert(d == 1);
vector<int> arr(n);
for(int &a : arr)
cin >> a;
tree.init(n);
vector<int> l(n, -1);
{
stack<int, vector<int>> st;
for(int i = 0; i < n; i++) {
while(!st.empty() && arr[st.top()] < arr[i])
st.pop();
if(!st.empty())
l[i] = st.top();
st.push(i);
}
}
for(int i = 0; i < n; i++)
tree.edt(l[i] + 1, i + 1, 1);
cout << tree.que() << '\n';
}
# | 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... |