이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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, ans[1000002];
pii y[1000002], h[1000002];
ll ctFlights(int mount) {
return 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... |