QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #18820 | #1877. Matryoshka Dolls | 1789 | RE | 31ms | 21056kb | C++20 | 2.9kb | 2022-01-27 13:58:14 | 2022-05-06 02:45:30 |
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: 2ms
memory: 15956kb
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: 0ms
memory: 13928kb
input:
1 1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 31ms
memory: 21056kb
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: 1ms
memory: 15844kb
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: 2ms
memory: 15952kb
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: 6ms
memory: 15872kb
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: 3ms
memory: 15952kb
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: 2ms
memory: 15980kb
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: 4ms
memory: 16020kb
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...