QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #53887 | #4808. Great Party | Pdw2007# | WA | 3ms | 3812kb | C++ | 955b | 2022-10-06 10:35:36 | 2022-10-06 10:35:37 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+1e3,M=(1<<20);
int n,m;
long long res;
int a[N],cnt[N<<5];
struct Query{int l,r,id;}q[N];
int bel[N];
long long ans[N];
void add(int x){res+=cnt[a[x]]++;}
void del(int x){res-=--cnt[a[x]];}
signed main()
{
scanf("%lld%lld",&n,&m);int B=sqrt(m);
a[0]=M;
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]),a[i]=((a[i]|M)-1)^a[i-1];
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&q[i].l,&q[i].r),q[i].id=i;
q[i].l--;
bel[i]=(i+B-1)/B;
}
sort(q+1,q+n,[&](const Query x,const Query y){return bel[x.l]==bel[y.l]?x.r<y.r:x.l<y.l;});
for(int i=1,l=1,r=0;i<=m;i++)
{
while(r<q[i].r)add(++r);
while(l>q[i].l)add(--l);
while(r>q[i].r)del(r--);
while(l<q[i].l)del(l++);
ans[q[i].id]=1ll*(q[i].r-q[i].l)*(q[i].r-q[i].l+1)/2-res;
}
for(int i=1;i<=m;i++)printf("%lld ",ans[i]);
return 0;
}
/*
4 5
1 2 2 4
1 2
2 3
3 4
1 3
2 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3728kb
input:
4 5 1 2 2 4 1 2 2 3 3 4 1 3 2 4
output:
3 2 3 5 5
result:
ok 5 number(s): "3 2 3 5 5"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3812kb
input:
4 5 5 6 7 8 1 2 2 3 3 4 1 3 2 4
output:
3 3 3 6 6
result:
ok 5 number(s): "3 3 3 6 6"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
10 10 3 7 3 1 6 6 10 3 3 3 9 10 5 10 3 7 5 6 5 6 9 10 3 10 1 4 6 6 1 4
output:
2 18 14 2 2 2 33 10 1 10
result:
ok 10 numbers
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 3780kb
input:
10 8 91 63 1 34 50 11 10 73 96 67 5 9 2 7 2 5 4 7 1 10 3 3 1 4 5 10
output:
15 21 10 10 55 1 10 0
result:
wrong answer 8th numbers differ - expected: '21', found: '0'