QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #18824 | #1877. Matryoshka Dolls | wenkaijie | WA | 16ms | 5108kb | C++ | 3.5kb | 2022-01-27 13:59:02 | 2022-05-06 02:45:54 |
Judging History
answer
# include <bits/stdc++.h>
# define N 500005
# define lowbit(x) (x&(-x))
using namespace std;
int n,m,logn,S;
long long nowans=0;
int a[N],pos[N],ans[N];
bool flag=1;
int l=1,r=0,cnt=0;
struct ask
{
int l,r,b,id;
bool operator <(const ask x)const
{
if(b==x.b)
if(b%2)
return r<x.r;
else
return r>x.r;
return b<x.b;
}
}q[N];
int minposl[N][40],maxposl[N][40],minposr[N][40],maxposr[N][40];
struct BIT
{
int sum[N];
void add(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i))
sum[i]+=y;
}
int getsum(int x)
{
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
ans+=sum[i];
return ans;
}
int getpos(int x)
{
int ans=0,now=0;
for(int i=logn;i>=0;i--)
{
if(ans+(1<<i)<=n && now+sum[ans+(1<<i)]<x)
{
ans+=(1<<i);
now+=sum[ans];
}
}
return ans+1;
}
}T;
void add(int x)
{
if(flag)
{
if(x==r+1)
nowans+=2*min(minposl[x][min(x-l,35)],maxposl[x][min(x-l,35)]);
else
nowans+=2*min(minposr[x][min(r-x,35)],maxposr[x][min(r-x,35)]);
}
if(cnt==0)
{
cnt++;
T.add(a[x],1);
return ;
}
int now=T.getsum(a[x]);
if(now==0)
{
int nowr=T.getpos(1);
nowans+=abs(x-pos[nowr]);
cnt++;
T.add(a[x],1);
return ;
}
if(now==cnt)
{
int nowl=T.getpos(cnt);
nowans+=abs(x-pos[nowl]);
cnt++;
T.add(a[x],1);
return ;
}
int nowl=T.getpos(now),nowr=T.getpos(now+1);
nowans+=2*min(abs(x-pos[nowl]),abs(x-pos[nowr]));
cnt++;
T.add(a[x],1);
return ;
}
void del(int x)
{
if(flag)
{
if(x==r)
nowans-=2*min(minposl[x][min(x-l,35)],maxposl[x][min(x-l,35)]);
else
nowans-=2*min(minposr[x][min(r-x,35)],maxposr[x][min(r-x,35)]);
}
if(cnt==1)
{
cnt--;
T.add(a[x],-1);
return ;
}
int now=T.getsum(a[x]);
if(now==1)
{
int nowr=T.getpos(2);
nowans-=abs(x-pos[nowr]);
cnt--;
T.add(a[x],-1);
return ;
}
if(now==cnt)
{
int nowl=T.getpos(cnt-1);
nowans-=abs(x-pos[nowl]);
cnt--;
T.add(a[x],-1);
return ;
}
int nowl=T.getpos(now-1),nowr=T.getpos(now+1);
nowans-=2*min(abs(x-pos[nowl]),abs(x-pos[nowr]));
cnt--;
T.add(a[x],-1);
return ;
}
int main()
{
cin>>n>>m;
logn=log2(n);
S=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
pos[a[i]]=i;
if(abs(a[i]-i)>10)
flag=0;
}
if(flag)
{
for(int i=1;i<=n;i++)
{
for(int j=i-1;j>=max(i-35,1);j--)
{
if(a[j]>a[i])
{
maxposl[i][i-j]=maxposl[i][i-j+1];
if(a[j]<a[minposl[i][i-j+1]])
minposl[i][i-j]=j;
else
minposl[i][i-j]=minposl[i][i-j+1];
}
else
{
minposl[i][i-j]=minposl[i][i-j+1];
if(a[j]>a[maxposl[i][i-j+1]])
maxposl[i][i-j]=j;
else
maxposl[i][i-j]=maxposl[i][i-j+1];
}
}
for(int j=i+1;j>=max(i+35,n);j--)
{
if(a[j]>a[i])
{
maxposr[i][j-i]=maxposr[i][j-i+1];
if(a[j]<a[minposr[i][j-i+1]])
minposr[i][j-i]=j;
else
minposr[i][j-i]=minposr[i][j-i+1];
}
else
{
minposr[i][j-i]=minposr[i][j-i+1];
if(a[j]>a[maxposr[i][j-i+1]])
maxposr[i][j-i]=j;
else
maxposr[i][j-i]=maxposr[i][j-i+1];
}
}
}
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].b=(q[i].l-1)/S+1;
q[i].id=i;
}
sort(q+1,q+m+1);
for(int i=1;i<=m;i++)
{
while(q[i].r>r)
add(r+1),r++;
while(q[i].l<l)
add(l-1),l--;
while(q[i].r<r)
del(r),r--;
while(q[i].l>l)
del(l),l++;
ans[q[i].id]=nowans;
}
for(int i=1;i<=m;i++)
printf("%lld\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3860kb
input:
5 5 1 5 2 4 3 1 5 1 4 1 3 1 2 1 1
output:
7 5 3 1 0
result:
ok 5 number(s): "7 5 3 1 0"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
1 1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 16ms
memory: 5108kb
input:
100000 1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 ...
output:
704982704
result:
wrong answer 1st numbers differ - expected: '4999950000', found: '704982704'