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 ll long long
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
int n, q;
ll ans[1000002];
pii y[1000002], h[1000002];
ll ctFlights(int mount) {
return (ll)mount*(mount+1)/2;
}
int dsu[1000002], sz[1000002];
bool over[1000002];
int par(int x) {
if(dsu[x]==0) return x;
else return dsu[x] = par(dsu[x]);
}
ll curct;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>q;
for(int i=1;i<=n;i++) {
cin>>h[i].f;
h[i].s = i;
}
sort(h+1, h+n+1);
for(int i=1;i<=q;i++) {
cin>>y[i].f;
y[i].s = i;
}
sort(y+1, y+q+1);
int hi = 1;
for(int yi=1;yi<=q;yi++) {
while(hi<=n && h[hi].f<=y[yi].f) {
over[h[hi].s] = 1;
sz[h[hi].s] = 1;
if(h[hi].s+1<=n && over[h[hi].s+1]) {
int p = par(h[hi].s+1);
curct -= ctFlights(sz[p]);
dsu[p] = h[hi].s;
sz[h[hi].s] += sz[p];
}
if(h[hi].s-1>=1 && over[h[hi].s-1]) {
int p = par(h[hi].s-1);
curct -= ctFlights(sz[p]);
dsu[h[hi].s] = p;
sz[p] += sz[h[hi].s];
}
curct += ctFlights(sz[par(h[hi].s)]);
hi++;
}
ans[y[yi].s] = curct;
}
for(int i=1;i<=q;i++) {
cout<<ans[i]<<'\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... |
# | 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... |