#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int mx=1e6+9;
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>s;
int n,q;
ll siz[mx],par[mx],a[mx],done[mx],anss[mx];
ll ans;
void init(){
for(int i=1;i<=n;i++){
par[i]=i;
siz[i]=1;
}
}
int Find(int node){
if(par[node]==node){
return node;
}
return par[node]=Find(par[node]);
}
void uni(int x,int y){
x=Find(x);
y=Find(y);
if(x==y){return;}
if(siz[x]>siz[y]){
swap(x,y);
}
ans+=siz[x]*siz[y];
par[x]=y;
siz[y]+=siz[x];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<pair<int,int>>v;
vector<pair<int,int>>query;
cin>>n>>q;
init();
for(int i=1; i<=n; i++)
{
cin>>a[i];
v.push_back({a[i],i});
}
sort(v.begin(),v.end());
for(int i=0; i<q; i++)
{ int x;
cin>>x;
query.push_back({x,i});
}
sort(query.begin(),query.end());
int j=0;
for(int i=0;i<q;i++){
while(j<n&&v[j].first<=query[i].first){
ans++;
int idx=v[j].second;
if(idx>0&&done[idx-1]){
// cout<<"TESR "<<idx<<endl;
uni(idx-1,idx);
}
if(idx<n&&done[idx+1]){
uni(idx+1,idx);
}
j++;
done[idx]=1;
}
// cout<<query[i].first<<" "<<query[i].second<<" "<<ans<<endl;
anss[query[i].second]=ans;
}
for(int i=0;i<q;i++){
cout<<anss[i]<<"\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
4808 KB |
Output is correct |
2 |
Correct |
29 ms |
4996 KB |
Output is correct |
3 |
Correct |
22 ms |
4680 KB |
Output is correct |
4 |
Correct |
24 ms |
4560 KB |
Output is correct |
5 |
Correct |
21 ms |
4552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
7612 KB |
Output is correct |
2 |
Correct |
37 ms |
7760 KB |
Output is correct |
3 |
Correct |
38 ms |
7644 KB |
Output is correct |
4 |
Correct |
40 ms |
7828 KB |
Output is correct |
5 |
Correct |
45 ms |
7612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
7756 KB |
Output is correct |
2 |
Correct |
37 ms |
7808 KB |
Output is correct |
3 |
Correct |
37 ms |
7772 KB |
Output is correct |
4 |
Correct |
38 ms |
7944 KB |
Output is correct |
5 |
Correct |
38 ms |
8008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
27 ms |
4808 KB |
Output is correct |
12 |
Correct |
29 ms |
4996 KB |
Output is correct |
13 |
Correct |
22 ms |
4680 KB |
Output is correct |
14 |
Correct |
24 ms |
4560 KB |
Output is correct |
15 |
Correct |
21 ms |
4552 KB |
Output is correct |
16 |
Correct |
18 ms |
4564 KB |
Output is correct |
17 |
Correct |
18 ms |
4984 KB |
Output is correct |
18 |
Correct |
20 ms |
4916 KB |
Output is correct |
19 |
Correct |
17 ms |
4532 KB |
Output is correct |
20 |
Correct |
19 ms |
4904 KB |
Output is correct |
21 |
Correct |
20 ms |
4532 KB |
Output is correct |
22 |
Correct |
20 ms |
4688 KB |
Output is correct |
23 |
Correct |
18 ms |
4936 KB |
Output is correct |
24 |
Correct |
18 ms |
4612 KB |
Output is correct |
25 |
Correct |
19 ms |
4832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
27 ms |
4808 KB |
Output is correct |
27 |
Correct |
29 ms |
4996 KB |
Output is correct |
28 |
Correct |
22 ms |
4680 KB |
Output is correct |
29 |
Correct |
24 ms |
4560 KB |
Output is correct |
30 |
Correct |
21 ms |
4552 KB |
Output is correct |
31 |
Correct |
38 ms |
7612 KB |
Output is correct |
32 |
Correct |
37 ms |
7760 KB |
Output is correct |
33 |
Correct |
38 ms |
7644 KB |
Output is correct |
34 |
Correct |
40 ms |
7828 KB |
Output is correct |
35 |
Correct |
45 ms |
7612 KB |
Output is correct |
36 |
Correct |
38 ms |
7756 KB |
Output is correct |
37 |
Correct |
37 ms |
7808 KB |
Output is correct |
38 |
Correct |
37 ms |
7772 KB |
Output is correct |
39 |
Correct |
38 ms |
7944 KB |
Output is correct |
40 |
Correct |
38 ms |
8008 KB |
Output is correct |
41 |
Correct |
18 ms |
4564 KB |
Output is correct |
42 |
Correct |
18 ms |
4984 KB |
Output is correct |
43 |
Correct |
20 ms |
4916 KB |
Output is correct |
44 |
Correct |
17 ms |
4532 KB |
Output is correct |
45 |
Correct |
19 ms |
4904 KB |
Output is correct |
46 |
Correct |
20 ms |
4532 KB |
Output is correct |
47 |
Correct |
20 ms |
4688 KB |
Output is correct |
48 |
Correct |
18 ms |
4936 KB |
Output is correct |
49 |
Correct |
18 ms |
4612 KB |
Output is correct |
50 |
Correct |
19 ms |
4832 KB |
Output is correct |
51 |
Correct |
45 ms |
7728 KB |
Output is correct |
52 |
Correct |
45 ms |
7560 KB |
Output is correct |
53 |
Correct |
49 ms |
7752 KB |
Output is correct |
54 |
Correct |
50 ms |
7552 KB |
Output is correct |
55 |
Correct |
46 ms |
7752 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
27 ms |
4808 KB |
Output is correct |
27 |
Correct |
29 ms |
4996 KB |
Output is correct |
28 |
Correct |
22 ms |
4680 KB |
Output is correct |
29 |
Correct |
24 ms |
4560 KB |
Output is correct |
30 |
Correct |
21 ms |
4552 KB |
Output is correct |
31 |
Correct |
38 ms |
7612 KB |
Output is correct |
32 |
Correct |
37 ms |
7760 KB |
Output is correct |
33 |
Correct |
38 ms |
7644 KB |
Output is correct |
34 |
Correct |
40 ms |
7828 KB |
Output is correct |
35 |
Correct |
45 ms |
7612 KB |
Output is correct |
36 |
Correct |
38 ms |
7756 KB |
Output is correct |
37 |
Correct |
37 ms |
7808 KB |
Output is correct |
38 |
Correct |
37 ms |
7772 KB |
Output is correct |
39 |
Correct |
38 ms |
7944 KB |
Output is correct |
40 |
Correct |
38 ms |
8008 KB |
Output is correct |
41 |
Correct |
18 ms |
4564 KB |
Output is correct |
42 |
Correct |
18 ms |
4984 KB |
Output is correct |
43 |
Correct |
20 ms |
4916 KB |
Output is correct |
44 |
Correct |
17 ms |
4532 KB |
Output is correct |
45 |
Correct |
19 ms |
4904 KB |
Output is correct |
46 |
Correct |
20 ms |
4532 KB |
Output is correct |
47 |
Correct |
20 ms |
4688 KB |
Output is correct |
48 |
Correct |
18 ms |
4936 KB |
Output is correct |
49 |
Correct |
18 ms |
4612 KB |
Output is correct |
50 |
Correct |
19 ms |
4832 KB |
Output is correct |
51 |
Correct |
45 ms |
7728 KB |
Output is correct |
52 |
Correct |
45 ms |
7560 KB |
Output is correct |
53 |
Correct |
49 ms |
7752 KB |
Output is correct |
54 |
Correct |
50 ms |
7552 KB |
Output is correct |
55 |
Correct |
46 ms |
7752 KB |
Output is correct |
56 |
Correct |
527 ms |
73188 KB |
Output is correct |
57 |
Correct |
577 ms |
73796 KB |
Output is correct |
58 |
Correct |
534 ms |
69308 KB |
Output is correct |
59 |
Correct |
521 ms |
70872 KB |
Output is correct |
60 |
Correct |
544 ms |
75512 KB |
Output is correct |