QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #18921 | #1877. Matryoshka Dolls | 1ink | WA | 88ms | 18720kb | C++17 | 3.3kb | 2022-01-27 15:10:53 | 2022-05-06 03:17:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e5+5;
set<int> treap,tmp;
ll read(){
ll x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x;
}
ll abz(int x){
if(x>0) return x;
return -x;
}
int cnt;
ll n,m;
ll lst[N];
ll ps[N];
struct Q{
int l,r,b,id;
}qs[N];
bool cmp(Q x,Q y){
if(x.b==y.b) return x.r<y.r;
return x.b<y.b;
}
ll sz;
ll ans;
ll res[N];
int j=1;
int trget_pre(int x){
if(treap.empty()) return 0;
auto it=treap.upper_bound(x);
if(it==treap.begin()) return 0;
it--;
return *it;
}
int trget_nxt(int x){
if(treap.empty()) return 0;
auto it=treap.upper_bound(x);
if(it==treap.end()) return 0;
return *it;
}
int tget_pre(int x){
if(treap.empty()) return 0;
auto it=treap.upper_bound(x);
if(it==treap.begin()) return 0;
it--;
return *it;
}
int tget_nxt(int x){
if(treap.empty()) return 0;
auto it=treap.upper_bound(x);
if(it==treap.end()) return 0;
return *it;
}
void add(int pos){
cnt++;
//if(j==2052) cout<<pos<<endl;
int a=trget_pre(lst[pos]),b=trget_nxt(lst[pos]);
treap.insert(lst[pos]);
//cout<<pos<<endl;
//cout<<lst[pos]<< ' '<<ans<<endl;
if(!a||!b){
if(!a&&!b) return;
ans+=abz(ps[a+b]-pos);
return;
}
else{
ans+=2*min(abz(ps[a]-pos),abz(ps[b]-pos));
return;
}
}
void del(int pos){
cnt++;
//if(j==2053||j==2052) cout<<pos<<endl;
treap.erase(treap.lower_bound(lst[pos]));
//cout<<"?\n";
}
void solve(int l,int r,int id){
ll ans=0;
for(int i=l;i<=r;i++){
cnt++;
int a=tget_pre(lst[i]),b=tget_nxt(lst[i]);
tmp.insert(lst[i]);
if(!a&&!b) continue;
if(!a||!b){
ans+=abz(ps[a+b]-i);
}
else{
ans+=2*min(abz(ps[a]-i),abz(ps[b]-i));
}
}
for(int i=l;i<=r;i++) tmp.erase(tmp.lower_bound(lst[i]));
res[id]=ans;
}
bool cmp1(Q a,Q b){
if(a.l==b.l) return a.r<b.r;
return a.l<b.l;
}
void slove(){
sort(qs+1,qs+1+m,cmp1);
int posi=0;
for(int i=1;i<=n;i++){
add(i);
for(int j=i+1;j<=n;j++){
add(j);
res[qs[++posi].id]=ans;
}
ans=0;
for(int j=i;j<=n;j++) del(j);
}
for(int i=1;i<=m;i++) printf("%lld\n",res[i]);
}
int main(){
// freopen("rrads.in","r",stdin);
// freopen("rrads.out","w",stdout);
n=read(),m=read();
sz=sqrt(n);
for(int i=1;i<=n;i++) lst[i]=read(),ps[lst[i]]=i;
for(int i=1;i<=m;i++){
qs[i].l=read(),qs[i].r=read();
qs[i].b=qs[i].l/sz,qs[i].id=i;
}
if(m==n*(n-1)/2){
slove();
return 0;
}
sort(qs+1,qs+1+m,cmp);
for(int i=0;i<=n/sz;i++){
//cout<<i<<endl;
int r=min(i*sz+sz,n),l=r+1;
int lpos=r;
ans=0;
//cout<<endl<<endl<<endl;
while(qs[j].b==i){
//cout<<j<<' '<<qs[j].l<<' '<<qs[j].r<<endl;
if(qs[j].b==qs[j].r/sz){
solve(qs[j].l,qs[j].r,qs[j].id);
++j;
continue;
}
//cout<<"WARNING"<<treap.sz[treap.root]<<endl;
while(r<qs[j].r) add(++r);
ll nw=ans;
while(l>qs[j].l) add(--l);
//cout<<l<<'*'<<r<<' '<<qs[j].id<<' '<<ans<<endl;
res[qs[j].id]=ans;
ans=nw;
while(l!=lpos+1) del(l++);
j++;
}
while(r!=lpos) del(r--);
}
// solve(3,4,1);
// solve(2,5,2);
//cout<<endl;
for(int i=1;i<=m;i++){
printf("%lld\n",res[i]);
}
//cout<<cnt<<endl;
return 0;
}
/*
5 2
5 4 2 3 1
3 4
2 5
5 10
5 4 2 3 1
3 4
2 5
1 2
1 3
1 4
1 5
2 3
2 4
3 5
4 5
*/
详细
Test #1:
score: 100
Accepted
time: 28ms
memory: 9876kb
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: 9812kb
input:
1 1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 88ms
memory: 18720kb
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: 9852kb
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: -100
Wrong Answer
time: 4ms
memory: 9856kb
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 0 8 22 3 0
result:
wrong answer 6th numbers differ - expected: '3', found: '0'