QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #693874 | #9327. Permutation and Queries | lytqwq# | WA | 2ms | 9256kb | C++14 | 2.1kb | 2024-10-31 16:53:45 | 2024-10-31 16:53:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,q,p[N],wz[N];
int L;
long long ans[N];
multiset<int> dk[N];
long long ask(){
long long ans=1e9;
for(int i=1;i<=L;i++){
int x=(*dk[i].begin());
ans=min(ans,i*1ll*x);
}
return ans;
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
wz[p[i]]=i;
}
L=2*sqrt(n);
for(int i=1;i<=L;i++){
for(int v=1;v+i<=n;v++){
dk[i].insert(abs(p[v+i]-p[v]));
dk[i].insert(abs(wz[v+i]-wz[v]));
}
}
printf("%lld\n",ask());
// ans[0]=ask();
for(int i=1;i<=q;i++){
int l,r;
scanf("%d%d",&l,&r);
if(l>r)swap(l,r);
for(int v=1;v<=L;v++){
if(l+v<=n)
dk[v].erase(dk[v].find(abs(p[l+v]-p[l])));
if(r+v<=n)
dk[v].erase(dk[v].find(abs(p[r+v]-p[r])));
if(l+v!=r)
if(r-v>=1)
dk[v].erase(dk[v].find(abs(p[r-v]-p[r])));
if(l-v>=1)
dk[v].erase(dk[v].find(abs(p[l-v]-p[l])));
if(p[l]+v<=n)
dk[v].erase(dk[v].find(abs(l-wz[p[l]+v])));
if(p[l]-v>=1)
dk[v].erase(dk[v].find(abs(l-wz[p[l]-v])));
if(p[r]+v!=p[l])
if(p[r]+v<=n)
dk[v].erase(dk[v].find(abs(r-wz[p[r]+v])));
if(p[r]-v!=p[l])
if(p[r]-v>=1)
dk[v].erase(dk[v].find(abs(r-wz[p[r]-v])));
// if(r+v<=n)
// dk[v].erase(dk[v].find(abs(p[r+v]-p[r])));
// if(l+v!=r)
// if(r-v>=1)
// dk[v].erase(dk[v].find(abs(p[r-v]-p[r])));
// if(l-v>=1)
// dk[v].erase(dk[v].find(abs(p[l-v]-p[l])));
}
swap(p[l],p[r]);
swap(wz[p[l]],wz[p[r]]);
for(int v=1;v<=L;v++){
if(l+v<=n)
dk[v].insert(abs(p[l+v]-p[l]));
if(r+v<=n)
dk[v].insert(abs(p[r+v]-p[r]));
if(l+v!=r)
if(r-v>=1)
dk[v].insert(abs(p[r-v]-p[r]));
if(l-v>=1)
dk[v].insert(abs(p[l-v]-p[l]));
if(p[l]+v<=n)
dk[v].insert(abs(l-wz[p[l]+v]));
if(p[l]-v>=1)
dk[v].insert(abs(l-wz[p[l]-v]));
if(p[r]+v!=p[l])
if(p[r]+v<=n)
dk[v].insert(abs(r-wz[p[r]+v]));
if(p[r]-v!=p[l])
if(p[r]-v>=1)
dk[v].insert(abs(r-wz[p[r]-v]));
}
printf("%lld\n",ask());
// ans[i]=ask();
}
}
/*
6 5
2 4 1 6 3 5
1 2
3 5
1 2
5 3
5 6
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9256kb
input:
6 5 2 4 1 6 3 5 1 2 3 5 1 2 5 3 5 6
output:
2 1 1 1 2 1
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 8740kb
input:
10 20 1 4 7 10 2 5 8 3 6 9 10 1 5 7 1 2 5 3 6 3 9 4 3 4 9 6 8 4 9 6 8 7 3 8 10 7 2 7 3 7 5 9 7 6 4 6 2 10 8 9
output:
3 3 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1
result:
ok 21 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 9056kb
input:
5 6 1 3 5 2 4 2 4 1 3 2 4 1 4 2 3 4 2
output:
2 1 1 1 1 1 2
result:
ok 7 numbers
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 8660kb
input:
4 4 1 3 2 4 1 2 3 1 1 3 2 3
output:
0 0 0 0 0
result:
wrong answer 1st numbers differ - expected: '1', found: '0'