This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
long long int n, q, a[N], b[N], fenwick[N];
void upd(int node, ll val){
for(int i = node; i <= q; i += (i & -i))
fenwick[i] += val;
}
ll query(int node){
long long int sum = 0;
for(int i = node; i >= 1; i -= (i & -i))
sum += fenwick[i];
return sum;
}
void solve(){
cin >> n >> q;
for(int i = 1; i <= n; ++i)
cin >> a[i];
vector<pair<int, int> > v;
v.push_back({0, 0});
for(int i = 1; i <= q; ++i){
cin >> b[i];
v.push_back({b[i], i});
}
int pre_greater[n + 1];
stack<int> st;
for(int i = n; i >= 1; --i){
while(!st.empty() and a[st.top()] < a[i]){
pre_greater[st.top()] = i;
st.pop();
}
st.push(i);
}
while(!st.empty()){
pre_greater[st.top()] = 0;
st.pop();
}
stack<int> stk;
int nxt_greater[n + 1];
for(int i = 1; i <= n; ++i){
while(!stk.empty() && a[stk.top()] <= a[i]){
nxt_greater[stk.top()] = i;
stk.pop();
}
stk.push(i);
}
while(!stk.empty()){
nxt_greater[stk.top()] = n + 1;
stk.pop();
}
sort(v.begin(), v.end());
for(ll i = 1; i <= n; ++i){
ll j = pre_greater[i], k = nxt_greater[i];
ll mx = a[i];
ll low = 1, high = v.size(), ans = -1;
while(low <= high){
int mid = (low + high) / 2;
if(v[mid].first >= mx){
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
if(ans == -1) continue;
upd(ans, (i - j)*(k - i));
}
ll ans[q + 1];
for(int i = 1; i <= q; ++i)
ans[v[i].second] = query(i);
for(int i = 1; i <= q; ++i)
cout << ans[i] << "\n";
}
int main(){
fast;
int t = 1;
// cin >> t;
while(t--)
solve();
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... |
# | 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... |