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>
using namespace std;
#define f first
#define s second
vector<int> g[1111111];
set<pair<int,int>> s;
int a[1111111];
long long ans[1111111],ind[1111111];
int main()
{
int n,q,hmx=0;
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++)
ind[i]=ind[i-1]+i;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
hmx=max(hmx,a[i]);
g[a[i]].push_back(i);
}
//s.insert({0,0});
for(int i=1;i<=hmx;i++)
{
ans[i]=ans[i-1];
//printf("Y");
for(auto x:g[i])
{
//printf("OO");
if(s.empty()){
ans[i]+=1,s.insert({x,x});
continue;
}
int cnt=1,rch=0,lch=0;
auto it=s.lower_bound({x,x});
if(it==s.end()) rch=1;
auto itr=--it;
it++;
pair<int,int> left=*itr,right=*it;
/*for(auto p=s.begin();p!=s.end();p++)
printf("%d,%d ",(*p).f,(*p).s);*/
//printf("\n%d %d %d %d %d\n%d %d\n",x,left.f,left.s,right.f,right.s,lch,rch);
if(!rch&&left.s==x-1&&right.f==x+1)
{
ans[i]-=ind[left.s-left.f+1];
ans[i]-=ind[right.s-right.f+1];
ans[i]+=ind[right.s-left.f+1];
s.erase(it);
s.erase(itr);
s.insert({left.f,right.s});
}
else if(!rch&&right.f==x+1)
{
ans[i]-=ind[right.s-right.f+1];
ans[i]+=ind[right.s-x+1];
s.erase(it);
s.insert({x,right.s});
}
else if(left.s==x-1)
{
ans[i]-=ind[left.s-left.f+1];
ans[i]+=ind[x-left.f+1];
s.erase(itr);
s.insert({left.f,x});
}
else
ans[i]+=1,s.insert({x,x});
//printf("LL");
}
}
for(int i=1;i<=q;i++)
{
int qu;
scanf("%d",&qu);
if(qu>hmx) qu=hmx;
printf("%lld\n",ans[qu]);
}
/* for(int i=1;i<=hmx;i++)
printf("%lld ",ind[i]);*/
return 0;
}
Compilation message (stderr)
pilot.cpp: In function 'int main()':
pilot.cpp:33:17: warning: unused variable 'cnt' [-Wunused-variable]
33 | int cnt=1,rch=0,lch=0;
| ^~~
pilot.cpp:33:29: warning: unused variable 'lch' [-Wunused-variable]
33 | int cnt=1,rch=0,lch=0;
| ^~~
pilot.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | scanf("%d %d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~~
pilot.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | scanf("%d",&a[i]);
| ~~~~~^~~~~~~~~~~~
pilot.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d",&qu);
| ~~~~~^~~~~~~~~~
# | 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... |