QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #845532 | #9971. 新本格魔法少女りすか | pwx2009 | 0 | 152ms | 15816kb | C++14 | 6.6kb | 2025-01-06 17:00:52 | 2025-01-06 17:00:52 |
Judging History
answer
#include<cstdio>
#define ll long long
#define lowbit(x) (x&(-x))
static const int BUF = 1<<20;
inline char gc() {
static char buf[BUF],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,BUF,stdin),p1==p2)?-1:*p1++;
}
inline int read(){
int num=0;
char ch;ch=gc();
while(ch<48||ch>57)ch=gc();
while(ch>47&&ch<58){
num=(num<<1)+(num<<3)+(ch^48);
ch=gc();
}return num;
}
const int N=5e5+15;
int n,m,K,B=3160;
int pos[N],l[N],r[N];
int a[N];
int ql[N],qr[N],qid[N];
int s[N],S[N];
inline void put(register int x,register int val){
while(x<=n){
s[x]+=val;
x+=lowbit(x);
}
}
inline int ask(register int x){
int val=0;
while(x){
val+=s[x];
x-=lowbit(x);
}return val;
}
ll ans[N];
int main(){
n=read(),m=read();
for(register int i=1;i<=n;i++){
a[i]=read();
if(i>B)pos[i]=pos[i-B]+1;
if(!l[pos[i]])l[pos[i]]=i;
r[pos[i]]=i;
}
if(n+1>B)pos[n+1]=pos[n+1-B]+1;
if(!l[pos[n+1]])l[pos[n+1]]=n+1;
r[pos[n+1]]=n+1;
for(register int i=1,p;i<=m;i++){
p=read();
while(p--){
K++;
ql[K]=read(),qr[K]=read(),qid[K]=i;
}
}
// for(register int L=1,R=B;L<=n;L+=B,R+=B){
// for(register int i=L;i<=R;i++)s[a[i]]++;
// for(register int i=1;i<=n;i++)s[i]+=s[i-1];
// for(register int i=1;i<=n;i++){
// S[i]=S[i-1];
// if(i<L)S[i]+=R-L+1-s[a[i]];
// if(i>R)S[i]+=s[a[i]];
// }
// for(register int i=1,j=1;i<=K;i=j){
// register int flag=0;
// register ll sum=0;
// while(j<=K&&qid[j]==qid[i]){
// if(ql[j]<=L&&qr[j]>=R)flag=1;
// else{
// if(ql[j]>R&&l[pos[qr[j]+1]]>r[pos[ql[j]-1]])sum-=S[l[pos[qr[j]+1]]-1]-S[r[pos[ql[j]-1]]];
// sum+=S[qr[j]]-S[ql[j]-1];
// }j++;
// }if(flag)ans[qid[i]]+=sum;
// }
// for(register int i=n;i;i--)s[i]-=s[i-1];
// for(register int i=L;i<=R;i++)s[a[i]]--;
// }
for(register int i=1,j=1;i<=K;){
while(j<=K&&qid[j]==qid[i]){
if(r[pos[ql[j]-1]]<l[pos[qr[j]+1]]){
register int k(r[pos[ql[j]-1]]);
while(k-7>=ql[j]){
ans[qid[i]]+=ask(a[k]);
ans[qid[i]]+=ask(a[k-1]);
ans[qid[i]]+=ask(a[k-2]);
ans[qid[i]]+=ask(a[k-3]);
ans[qid[i]]+=ask(a[k-4]);
ans[qid[i]]+=ask(a[k-5]);
ans[qid[i]]+=ask(a[k-6]);
ans[qid[i]]+=ask(a[k-7]);
k-=8;
}while(k>=ql[j])ans[qid[i]]+=ask(a[k--]);
k=l[pos[qr[j]+1]];
while(k+7<=qr[j]){
ans[qid[i]]+=ask(a[k]);
ans[qid[i]]+=ask(a[k+1]);
ans[qid[i]]+=ask(a[k+2]);
ans[qid[i]]+=ask(a[k+3]);
ans[qid[i]]+=ask(a[k+4]);
ans[qid[i]]+=ask(a[k+5]);
ans[qid[i]]+=ask(a[k+6]);
ans[qid[i]]+=ask(a[k+7]);
k+=8;
}while(k<=qr[j])ans[qid[i]]+=ask(a[k++]);
k=r[pos[ql[j]-1]];
while(k-7>=ql[j]){
put(a[k],1);
put(a[k-1],1);
put(a[k-2],1);
put(a[k-3],1);
put(a[k-4],1);
put(a[k-5],1);
put(a[k-6],1);
put(a[k-7],1);
k-=8;
}while(k>=ql[j])put(a[k--],1);
k=l[pos[qr[j]+1]];
while(k+7<=qr[j]){
put(a[k],1);
put(a[k+1],1);
put(a[k+2],1);
put(a[k+3],1);
put(a[k+4],1);
put(a[k+5],1);
put(a[k+6],1);
put(a[k+7],1);
k+=8;
}while(k<=qr[j])put(a[k++],1);
}else{
register int k=ql[j];
while(k+7<=qr[j]){
ans[qid[i]]+=ask(a[k]);
ans[qid[i]]+=ask(a[k+1]);
ans[qid[i]]+=ask(a[k+2]);
ans[qid[i]]+=ask(a[k+3]);
ans[qid[i]]+=ask(a[k+4]);
ans[qid[i]]+=ask(a[k+5]);
ans[qid[i]]+=ask(a[k+6]);
ans[qid[i]]+=ask(a[k+7]);
k+=8;
}while(k<=qr[j])ans[qid[i]]+=ask(a[k++]);
k=ql[j];
while(k+7<=qr[j]){
put(a[k],1);
put(a[k+1],1);
put(a[k+2],1);
put(a[k+3],1);
put(a[k+4],1);
put(a[k+5],1);
put(a[k+6],1);
put(a[k+7],1);
k+=8;
}while(k<=qr[j])put(a[k++],1);
}++j;
}
while(i<j){
if(r[pos[ql[i]-1]]<l[pos[qr[i]+1]]){
register int k=r[pos[ql[i]-1]];
while(k-7>=ql[i]){
put(a[k],-1);
put(a[k-1],-1);
put(a[k-2],-1);
put(a[k-3],-1);
put(a[k-4],-1);
put(a[k-5],-1);
put(a[k-6],-1);
put(a[k-7],-1);
k-=8;
}while(k>=ql[i])put(a[k--],-1);
k=l[pos[qr[i]+1]];
while(k+7<=qr[i]){
put(a[k],-1);
put(a[k+1],-1);
put(a[k+2],-1);
put(a[k+3],-1);
put(a[k+4],-1);
put(a[k+5],-1);
put(a[k+6],-1);
put(a[k+7],-1);
k+=8;
}while(k<=qr[i])put(a[k++],-1);
}else{
register int k=ql[i];
while(k+7<=qr[i]){
put(a[k],-1);
put(a[k+1],-1);
put(a[k+2],-1);
put(a[k+3],-1);
put(a[k+4],-1);
put(a[k+5],-1);
put(a[k+6],-1);
put(a[k+7],-1);
k+=8;
}while(k<=qr[i])put(a[k++],-1);
}++i;
}
}for(register int i=1;i<=m;i++)printf("%lld\n",ans[i]);
}
詳細信息
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
500000 50174 453952 363686 491616 32825 57465 422945 471561 73291 421205 416554 23295 133266 242225 330448 25039 340064 28713 465664 162059 323880 28978 273728 101338 161413 294941 214275 63951 267981 294251 202822 253124 272510 3268 37918 139343 385983 111577 311901 487665 482827 347449 416029 3065...
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 10
Accepted
time: 152ms
memory: 15816kb
input:
500000 5 157360 289139 98034 293691 150262 268366 36782 147093 365410 444658 343224 375392 278298 357620 389673 167019 7747 119244 102126 83512 3649 459230 197365 245259 38071 249539 34617 213697 292553 389625 395778 280152 280038 239519 301475 232272 145919 370004 422791 271143 488283 185166 351026...
output:
50666226791 50440151159 50719090228 50631079493 50747050985
result:
ok 5 number(s): "50666226791 50440151159 50719090228 50631079493 50747050985"
Test #7:
score: 0
Wrong Answer
time: 135ms
memory: 15392kb
input:
500000 5 70752 248917 41910 13653 177839 45858 54229 174152 10090 332231 437916 391622 432270 53875 446421 91921 461870 243336 363086 249844 338371 495447 423857 350363 365324 255747 170681 435791 177298 199582 240768 449011 302158 378518 233809 267343 362784 187864 114604 322031 255693 54447 406202...
output:
48041849427 42899237633 48149375837 45139036063 62373267184
result:
wrong answer 2nd numbers differ - expected: '47573923544', found: '42899237633'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%