이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define MAX 500005
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define inf (1987654321)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
int n, q;
int arr[100005], l[100005], r[100005], ord[100005], chk[100005];
ll sum[100005];
pii tmp[100005];
void update_sum() {
for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + arr[i];
}
void update_sort(int idx) {
int j = 0, k = 0;
for(int i = 1; i <= n; ++i) if(ord[i] == idx) j = i;
for(int i = j; i < n; ++i) ord[i] = ord[i + 1];
for(int i = 1; i < n; ++i) if(arr[ord[i]] >= arr[idx]) k = i;
for(int i = n; i > k + 1; --i) ord[i] = ord[i - 1];
ord[k + 1] = idx;
}
void update_r() {
stack<int> st;
for(int i = 1; i <= n; ++i) r[i] = n + 1;
for(int i = 1; i <= n; ++i) {
while(!st.empty() && arr[st.top()] < arr[i]) {
r[st.top()] = i;
st.pop();
}
st.push(i);
}
}
void update_l() {
stack<int> st;
for(int i = 1; i <= n; ++i) l[i] = 0;
for(int i = n; i >= 1; --i) {
while(!st.empty() && arr[st.top()] < arr[i]) {
l[st.top()] = i;
st.pop();
}
st.push(i);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> arr[i];
for(int i = 1; i <= n; ++i) tmp[i] = {arr[i], i};
sort(tmp + 1, tmp + n + 1, greater<pii>());
for(int i = 1; i <= n; ++i) ord[i] = tmp[i].second;
update_sum(); update_l(); update_r();
cin >> q;
while(q--) {
int t, a, b; cin >> t >> a >> b;
if(t == 1) {
arr[a] = b;
update_sum(); update_l(); update_r();
update_sort(a);
}
else {
int ans = 0;
for(int i = 1; i <= n; ++i) chk[i] = 0;
for(int i = 1; i <= n; ++i) {
if(ord[i] < a || ord[i] > b) continue;
int lv = l[ord[i]] >= a ? arr[l[ord[i]]] : -1, li = max(l[ord[i]], a - 1);
int rv = r[ord[i]] <= b ? arr[r[ord[i]]] : -1, ri = min(r[ord[i]], b + 1);
ll sumv = sum[ri - 1] - sum[li];
if(lv == -1 && rv == -1) chk[ord[i]] = 1;
else if(lv != -1 && chk[li] && sumv >= lv) chk[ord[i]] = 1;
else if(rv != -1 && chk[ri] && sumv >= rv) chk[ord[i]] = 1;
ans += chk[ord[i]];
}
cout << ans << '\n';
}
}
return 0;
}
# | 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... |