Submission #1215621

#TimeUsernameProblemLanguageResultExecution timeMemory
121562112345678Pilot (NOI19_pilot)C++17
100 / 100
964 ms114116 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int nx=1e6+5; ll n, q, x, h[nx], ans, res[nx]; set<ll> s; vector<ll> vl[nx]; void add(ll idx) { auto nxt=*s.lower_bound(idx), pv=*prev(s.lower_bound(idx)); ans-=(nxt-pv)*(nxt-pv-1)/2; ans+=(idx-pv)*(idx-pv-1)/2; ans+=(nxt-idx)*(nxt-idx-1)/2; s.insert(idx); } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>q; s.insert(0), s.insert(n+1); ans=n*(n+1)/2; for (int i=1; i<=n; i++) cin>>h[i], vl[h[i]].push_back(i); for (int i=nx-2; i>=0; i--) { for (auto idx:vl[i+1]) add(idx); res[i]=ans; } while (q--) cin>>x, cout<<res[x]<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...