QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #18814 | #1877. Matryoshka Dolls | 1789 | RE | 36ms | 21192kb | C++14 | 2.9kb | 2022-01-27 13:56:38 | 2022-05-06 02:43:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int s=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
s=s*10+c-'0';
c=getchar();
}
return s*f;
}
void write(long long x)
{
if(x<0)
putchar('-'),x=-x;
if(x/10)
write(x/10);
putchar(x%10+'0');
}
int n,m,s,ns;
int num[500007],block[500007],l[717],r[717];
long long anss[500007];
struct Quest{
int l,r,dat;
}q[500007];
bool cmp2(Quest x,Quest y)
{
if(block[x.l]!=block[y.l])
return block[x.l]<block[y.l];
if(block[x.l]&1)
return x.r<y.r;
return x.r>y.r;
}
int wz[500007],L[500007],R[500007];
set <int> S;
long long ans=0;
int main()
{
//freopen("rrads.in","r",stdin);
//freopen("rrads.out","w",stdout);
n=read(),m=read();
s=n/sqrt(m),ns=n/s;
S.insert(0);
S.insert(1e9);
for(int i=1;i<=n;++i)
num[i]=read(),block[i]=(i-1)/s+1,wz[num[i]]=i;
for(int i=1;i<=ns;++i)
l[i]=(i-1)*s+1,r[i]=min(i*s,n);
for(int i=1;i<=m;++i)
q[i].l=read(),q[i].r=read(),q[i].dat=i;
sort(q+1,q+m+1,cmp2);
int l=1,r=0;
for(int ii=1;ii<=m;++ii)
{
while(r<q[ii].r)
{
++r;
int ll,rr;
S.insert(num[r]);
ll=*(--S.find(num[r])),rr=*(++S.find(num[r]));
if(ll>0&&ll<=n)
{
ans+=abs(r-wz[ll]);
R[ll]=num[r],L[num[r]]=ll;
}
if(rr>0&&rr<=n)
{
ans+=abs(r-wz[rr]);
L[rr]=num[r],R[num[r]]=rr;
}
if(ll>0&&ll<=n&&rr>0&&rr<=n)
ans-=abs(wz[ll]-wz[rr]);
// cout<<l<<" "<<r<<" "<<ans<<endl;
}
while(l>q[ii].l)
{
--l;
int ll,rr;
S.insert(num[l]);
ll=*(--S.find(num[l])),rr=*(++S.find(num[l]));
if(ll>0&&ll<=n)
{
ans+=abs(l-wz[ll]);
R[ll]=num[l],L[num[l]]=ll;
}
if(rr>0&&rr<=n)
{
ans+=abs(l-wz[rr]);
L[rr]=num[l],R[num[l]]=rr;
}
if(ll>0&&ll<=n&&rr>0&&rr<=n)
ans-=abs(wz[ll]-wz[rr]);
// cout<<l<<" "<<r<<" "<<ans<<endl;
}
while(r>q[ii].r)
{
R[L[num[r]]]=R[num[r]];
L[R[num[r]]]=L[num[r]];
int ll=L[num[r]],rr=R[num[r]];
if(ll>0&&ll<=n)
ans-=abs(r-wz[ll]);
if(rr>0&&rr<=n)
ans-=abs(r-wz[rr]);
if(ll>0&&ll<=n&&rr>0&&rr<=n)
ans+=abs(wz[rr]-wz[ll]);
S.erase(num[r]);
L[num[r]]=R[num[r]]=0;
--r;
//cout<<l<<" "<<r<<" "<<ans<<endl;
}
while(l<q[ii].l)
{
R[L[num[l]]]=R[num[l]];
L[R[num[l]]]=L[num[l]];
int ll=L[num[l]],rr=R[num[l]];
if(ll>0&&ll<=n)
ans-=abs(l-wz[ll]);
if(rr>0&&rr<=n)
ans-=abs(l-wz[rr]);
// cout<<ans<<endl;
if(ll>0&&ll<=n&&rr>0&&rr<=n)
ans+=abs(wz[rr]-wz[ll]);
S.erase(num[l]);
L[num[l]]=R[num[l]]=0;
++l;
// cout<<ll<<" "<<rr<<" "<<l<<" "<<r<<" "<<ans<<endl;
}
anss[q[ii].dat]=ans;
}
for(int i=1;i<=m;++i)
write(anss[i]),putchar('\n');
fclose(stdin);
fclose(stdout);
return 0;
}
/*
5 15
5 2 4 3 1
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 15968kb
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: 3ms
memory: 13784kb
input:
1 1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 36ms
memory: 21192kb
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:
4999950000
result:
ok 1 number(s): "4999950000"
Test #4:
score: 0
Accepted
time: 2ms
memory: 15980kb
input:
20 1 12 8 13 10 18 14 1 19 5 16 15 9 17 20 6 2 11 4 3 7 9 18
output:
36
result:
ok 1 number(s): "36"
Test #5:
score: 0
Accepted
time: 3ms
memory: 15840kb
input:
20 10 5 16 11 7 19 8 12 13 17 18 6 1 14 3 4 2 15 20 10 9 7 11 7 13 7 17 11 15 1 7 4 6 1 5 6 14 3 5 9 9
output:
7 16 34 9 20 3 8 22 3 0
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 2ms
memory: 13912kb
input:
20 50 7 3 13 8 9 18 1 15 12 10 20 11 17 16 2 19 5 4 6 14 3 6 5 15 11 20 10 18 9 20 3 17 13 20 16 17 3 20 4 17 15 18 5 19 3 14 8 20 2 20 1 4 15 19 16 20 5 13 14 17 4 10 6 16 8 16 1 12 4 9 11 15 4 20 8 11 3 16 7 7 3 11 3 7 4 4 5 12 6 20 3 14 6 19 6 19 2 14 2 12 5 6 4 6 8 15 10 19 4 14 1 16 1 20 2 13 3...
output:
6 48 36 24 46 74 17 1 104 64 5 68 44 58 130 5 9 8 30 7 13 48 26 38 11 8 92 5 70 0 28 9 0 20 80 44 58 58 48 36 1 2 20 28 34 76 136 46 1 28
result:
ok 50 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 15844kb
input:
20 100 4 13 20 8 1 18 19 9 17 5 12 7 11 16 6 3 15 10 14 2 4 19 1 6 6 19 4 6 2 17 1 5 11 13 1 15 9 17 9 15 7 20 3 19 10 19 1 10 11 17 10 17 2 18 17 20 12 19 1 3 5 17 7 13 6 18 10 20 1 6 2 17 5 9 4 13 11 13 2 20 7 13 12 17 5 19 17 20 11 19 3 15 3 5 5 11 1 17 10 15 16 20 1 6 2 19 4 12 5 18 9 17 3 6 12 ...
output:
76 16 57 3 84 10 3 74 31 19 59 80 40 44 16 26 94 5 26 2 54 17 53 44 16 84 8 32 3 106 17 12 68 5 30 48 2 16 102 14 9 16 98 28 64 31 6 1 54 20 26 31 74 5 26 3 66 32 36 59 1 26 6 33 35 5 57 1 1 57 24 6 10 68 36 41 34 0 12 8 11 2 62 12 41 10 5 25 0 60 0 44 25 12 8 2 16 36 8 1
result:
ok 100 numbers
Test #8:
score: 0
Accepted
time: 4ms
memory: 13924kb
input:
20 228 7 3 17 10 16 11 19 5 1 13 20 18 14 2 8 4 6 9 12 15 7 20 2 20 10 13 14 19 1 9 12 20 17 19 9 20 10 12 14 17 4 15 7 16 5 12 13 16 16 18 7 18 1 11 7 17 2 20 6 8 9 17 12 18 7 18 3 4 7 13 1 4 6 12 6 10 3 17 3 4 5 14 7 13 9 20 6 20 2 4 14 17 17 20 1 7 19 20 4 20 14 15 12 16 4 6 4 15 10 11 2 16 2 20 ...
output:
66 136 5 9 32 30 2 42 3 5 62 40 28 5 2 50 44 44 136 3 20 14 50 1 16 5 18 10 74 1 44 16 42 90 3 5 3 13 1 108 1 6 3 62 1 94 136 3 14 42 3 80 26 6 54 7 26 26 31 1 74 38 15 14 52 26 14 6 4 7 3 2 70 13 2 44 6 76 26 90 1 66 108 0 28 16 132 18 7 3 14 48 7 15 1 8 9 22 9 18 36 5 70 44 42 3 1 42 0 3 3 8 3 62 ...
result:
ok 228 numbers
Test #9:
score: 0
Accepted
time: 3ms
memory: 15960kb
input:
20 322 3 11 4 1 9 19 7 12 5 17 8 15 10 18 13 2 20 16 14 6 8 14 6 6 3 17 3 16 9 18 7 17 12 13 4 14 12 18 6 13 8 9 3 17 7 20 12 16 10 15 12 16 12 14 16 19 6 7 18 20 6 16 7 14 5 19 12 13 3 14 10 15 11 18 12 20 8 9 1 13 17 18 1 18 4 19 4 9 5 19 4 5 1 2 10 17 11 19 7 14 15 20 20 20 4 7 12 15 7 17 3 13 7 ...
output:
19 0 91 80 37 39 1 48 21 23 1 91 81 10 13 10 3 5 1 2 44 23 87 1 50 13 25 37 1 58 1 119 99 14 87 1 1 21 33 23 15 0 6 7 39 42 36 1 91 3 107 25 1 44 1 0 10 7 1 1 55 3 10 2 34 91 1 51 26 25 75 1 1 18 79 13 1 80 21 16 5 3 0 18 3 7 63 63 66 3 0 5 17 0 21 10 1 3 5 1 6 35 41 29 59 43 21 0 45 3 6 75 1 103 0 ...
result:
ok 322 numbers
Test #10:
score: -100
Runtime Error
input:
20 1000 16 6 17 1 12 11 5 8 10 19 4 18 2 9 14 7 15 3 20 13 1 6 8 9 9 11 5 18 3 20 2 9 17 18 12 12 12 20 5 17 1 8 10 10 2 9 17 19 1 7 7 15 12 19 2 7 9 14 2 14 1 4 15 17 11 19 2 5 3 12 11 14 11 14 13 17 7 8 9 18 2 11 8 11 1 4 4 8 12 13 12 19 7 16 12 16 11 15 5 9 5 18 2 19 11 15 1 15 4 20 4 9 5 14 5 19...