QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #18912 | #1877. Matryoshka Dolls | zfz | WA | 44ms | 12372kb | C++14 | 2.1kb | 2022-01-27 15:00:25 | 2022-05-06 03:13:53 |
Judging History
answer
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
template <class T>
inline T read(){
T r=0,f=0;char c=getchar();
while(!isdigit(c)) f|=c=='-',c=getchar();
while(isdigit(c)) r=(r<<3)+(r<<1)+(c^48),c=getchar();
return f?-r:r;
}
const int N=5e5+5;
int n,m,block,a[N];
struct query{
int l,r,id;
bool operator <(const query &x)const{
if(l/block==x.l/block) return r<x.r;
return l/block<x.l/block;
}
}Q[N];
int L=1,R=0,sum;
int ans[N];
struct node{
int id,val;
bool operator <(const node &x)const{
return val==x.val?id<x.id:val<x.val;
}
};
set<node> S;
void add(int x){
S.insert({x,a[x]});
auto it1=S.lower_bound({x,a[x]}),it2=S.upper_bound({x,a[x]}),it=S.lower_bound({x,a[x]});
if(it1--!=S.begin()&&it2!=S.end()) sum-=abs((*it1).id-(*it2).id);
if(it--!=S.begin()){sum+=abs((*it).id-x); /*cout<<"!!!"<<x<<" "<<(*it).id<<" "<<(*it).val<<" "<<x<<" "<<a[x]<<" "<<sum<<endl;*/}
if(it2!=S.end()){sum+=abs((*it2).id-x); /*cout<<"???"<<x<<" "<<(*it2).id<<" "<<(*it2).val<<" "<<sum<<endl;*/}
}
void del(int x){
auto it1=S.lower_bound({x,a[x]}),it2=S.upper_bound({x,a[x]}),it=S.lower_bound({x,a[x]});
if(it1--!=S.begin()&&it2!=S.end()) sum+=abs((*it1).id-(*it2).id);
if(it--!=S.begin()){sum-=abs((*it).id-x);/*cout<<"!!!"<<x<<" "<<(*it).id<<" "<<(*it).val<<" "<<x<<" "<<a[x]<<" "<<sum<<endl;*/}
if(it2!=S.end()){sum-=abs((*it2).id-x);/*cout<<"???"<<x<<" "<<(*it2).id<<" "<<(*it2).val<<" "<<sum<<endl;*/}
S.erase(S.find({x,a[x]}));
}
int main(){
n=read<int>(),m=read<int>(),block=sqrt(n);
for(int i=1;i<=n;++i) a[i]=read<int>();
for(int i=1;i<=m;++i) Q[i].l=read<int>(),Q[i].r=read<int>(),Q[i].id=i;
sort(Q+1,Q+1+m);
for(int i=1;i<=m;++i){
//cout<<Q[i].l<<" "<<Q[i].r<<" "<<Q[i].id<<endl;
//cout<<"D: "<<sum<<endl;
while(R<Q[i].r) add(++R);
//cout<<"D: "<<sum<<endl;
while(R>Q[i].r) del(R--);
while(L>Q[i].l) add(--L);
while(L<Q[i].l) del(L++);
ans[Q[i].id]=sum;
//for(auto v:S){
// cout<<v.id<<" "<<v.val<<endl;
//}
}
for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
return 0;
}
/*
5 2
5 4 2 3 1
3 4
2 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 7728kb
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: 7832kb
input:
1 1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 44ms
memory: 12372kb
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:
704982704
result:
wrong answer 1st numbers differ - expected: '4999950000', found: '704982704'