이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin >> n;
vector<int> a(n);
for(auto &i : a) cin >> i;
cin >> q;
for(int t, l, r, i = 0; i < q; i++) {
cin >> t >> l >> r;
--l;
if(t == 1) {
a[l] = r;
} else {
vector<int> die(n + 1);
auto add = [&](int l, int r) {
if(l < r) {
die[l]++;
die[r]--;
}
};
vector<array<ll, 2>> st;//{right, sum, blocked}
for(int i = l; i < r; i++) {
ll sum = 0;
while(st.size() && a[st.back()[0]] < a[i]) {
sum += st.back()[1] + a[st.back()[0]];
st.pop_back();
}
if(sum < a[i]) {
add(st.empty() ? l : st.back()[0] + 1, i);
}
st.push_back({i, sum});
}
st.clear();//{right, sum, blocked}
for(int i = r; i-- > l;) {
ll sum = 0;
while(st.size() && a[st.back()[0]] < a[i]) {
sum += st.back()[1] + a[st.back()[0]];
st.pop_back();
}
if(sum < a[i]) {//[i + 1; st.back())
add(i + 1, st.empty() ? n : st.back()[0]);
}
st.push_back({i, sum});
}//6 4 1 2 6
int ans = 0, cur = 0;
for(int i = l; i < r; i++) {
cur += die[i];
ans += !cur;
}
cout << ans << '\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... |