QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #18953 | #1877. Matryoshka Dolls | momo_li | WA | 5ms | 31964kb | C++ | 4.5kb | 2022-01-27 17:32:57 | 2022-05-06 03:24:01 |
Judging History
answer
#include<bits/stdc++.h>
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
// #define int long long
#define mod (998244353)
#ifndef ONLINE_JUDGE
#pragma GCC optimize(2)
#endif
using namespace std;
namespace IO{
inline int read(){
int n=0;
int s=1;
char x;
while((x=getchar())<'0'||x>'9')
if(x=='-')
s=-1;
while(x>='0'&&x<='9'){
n=(n<<1)+(n<<3)+(x^48),
x=getchar();
}
return n*s;
}
void write(char x){
putchar(x);
}
void write(const char *x){
for(;*x;++x)
putchar(*x);
}
void write(char *x){
for(;*x;++x)
putchar(*x);
}
void write(signed x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar('0'+x-x/10*10);
}
void write(long long x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar('0'+x-x/10*10);
}
void write(double x){
printf("%lf",x);
}
template<typename type1,typename type2,typename ...typen>
void write(type1 a1,type2 a2,typen ...an){
write(a1);
write(a2,an...);
}
}// namespace IO
inline long long max(long long a,long long b){return a>b?a:b;}
inline long long min(long long a,long long b){return a>b?b:a;}
// stop
struct List{
int a,l,r;
}notes[500001];
unsigned int tot;
unsigned int L[500001],R[500001];
unsigned int changed[500001],cnt;
bool qwq[500001];
unsigned int col[500001],cl[500001],cr[500001],len;
void init(int n){
int m=n/len;
for(int i=1;i<=n;i++)col[i]=(i-1)/len+1;
for(int i=1;i<=m;i++)cl[i]=len*(i-1)+1,cr[i]=len*i;
if(m*len<n)m++,cl[m]=len*(m-1)+1,cr[m]=n;
}
unsigned int pos[500001];
struct Node{
int l,r,id;
bool operator<(Node x){
if(col[l]==col[x.l])return r>x.r;
return col[l]<col[x.l];
}
}ques[500001];
unsigned long long ans[500001];
unsigned long long nowans;
unsigned int x[500001];
unsigned int p[500001];
inline int abs(int a){return a>=0?a:-a;}
void init2(int y,int n){
tot=0;
memset(notes,0,sizeof(notes));
memset(x,0,sizeof(x));
nowans=0;
for(int i=1;i<=n;i++)
if(pos[i]>=y){
// cout<<pos[i]<<" ";
tot++;
x[pos[i]]=tot;
notes[tot].l=tot-1,notes[tot].a=pos[i],L[tot]=tot-1;
if(tot-1)notes[tot-1].r=tot,nowans+=abs(notes[tot].a-notes[tot-1].a),R[tot-1]=tot;
}
// cout<<"\n";
}
signed main(){
using namespace IO;
// no define int long long
// freopen("rrads.in","r",stdin);
// freopen("rrads.out","w",stdout);
int n=read(),m=read();
len=n/sqrt(m)*2;
init(n);
for(int i=1;i<=n;i++)p[i]=read(),pos[p[i]]=i;
for(int i=1;i<=m;i++)ques[i].l=read(),ques[i].r=read(),ques[i].id=i;
sort(ques+1,ques+m+1);
int l,r;
for(int i=1;i<=m;i++){
if(i==1||col[ques[i].l]!=col[ques[i-1].l])
init2(cl[col[ques[i].l]],n),l=cl[col[ques[i].l]],r=n;
// if(col[ques[i].l]==col[ques[i].r]){
// continue;
// }
while(r>ques[i].r){
int po=x[r];
int lson=notes[po].l,rson=notes[po].r;
if(lson){
R[lson]=rson;
nowans-=abs(notes[po].a-notes[lson].a);
notes[lson].r=rson;
}
if(rson){
L[rson]=lson;
nowans-=abs(notes[po].a-notes[rson].a);
notes[rson].l=lson;
}
if(lson&&rson)nowans+=abs(notes[lson].a-notes[rson].a);
r--;
// cout<<nowans<<"\n";
}
// cout<<'\n';
long long poans=nowans;
while(l<ques[i].l){
int po=x[l];
int lson=notes[po].l,rson=notes[po].r;
// cout<<po<<"\n";
if(lson){
if(!qwq[lson])qwq[lson]=1,changed[++cnt]=lson;
poans-=abs(notes[po].a-notes[lson].a);
notes[lson].r=rson;
}
if(rson){
if(!qwq[rson])qwq[rson]=1,changed[++cnt]=rson;
poans-=abs(notes[po].a-notes[rson].a);
notes[rson].l=lson;
}
if(lson&&rson)poans+=abs(notes[lson].a-notes[rson].a);
l++;
}
ans[ques[i].id]=poans;
l=cl[col[ques[i].l]];
for(int j=1;j<=cnt;j++)
notes[changed[j]].l=L[changed[j]],notes[changed[j]].r=R[changed[j]],qwq[changed[j]]=0;
cnt=0;
}
for(int i=1;i<=m;i++)write((long long)ans[i],'\n');
return 0;
}
/*
---- ----
---- ----
---- ----
---- ----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
----
---- ----
---- ----
---- ----
---- ----
----------------------------------------
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 27700kb
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: 2ms
memory: 29420kb
input:
1 1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 2ms
memory: 31964kb
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: 29252kb
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: 1ms
memory: 31632kb
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: -100
Wrong Answer
time: 1ms
memory: 30640kb
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 -4 28 9 0 20 80 44 58 58 48 36 1 2 20 28 34 76 136 46 1 28
result:
wrong answer 30th numbers differ - expected: '0', found: '-4'