QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #845409 | #9971. 新本格魔法少女りすか | pwx2009 | 0 | 614ms | 17948kb | C++14 | 6.7kb | 2025-01-06 16:34:52 | 2025-01-06 16:34: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=ql[i];
while(k+7<=qr[i]){
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[i])ans[qid[i]]+=ask(a[k++]);
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);
}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]);
}
Details
Tip: Click on the bar to expand more detailed information
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: 0
Wrong Answer
time: 614ms
memory: 17948kb
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:
50790991953 56284377289 63558118739 69239024607 75678567387
result:
wrong answer 1st numbers differ - expected: '50666226791', found: '50790991953'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%