QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #693699 | #9327. Permutation and Queries | lytqwq# | WA | 0ms | 3984kb | C++14 | 1.1kb | 2024-10-31 16:35:37 | 2024-10-31 16:35:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,q,p[N];
int L;
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]);
}
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]));
}
}
printf("%lld\n",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])));
}
swap(p[l],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]));
}
printf("%lld\n",ask());
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3984kb
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: 3936kb
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: 3932kb
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: 3932kb
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'