QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #53140 | #4808. Great Party | Constant# | WA | 2ms | 3784kb | C++14 | 1.1kb | 2022-10-04 19:14:45 | 2022-10-04 19:14:47 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
int n,l=1,r,t,x,q,a[N],b[N],s[N];
ll A,B,now,ans[N],sum,cnt[30*N];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct node
{
ll l,r;
int id;
}c[N];
bool cmp(node x,node y){return b[x.l]^b[y.l]?b[x.l]<b[y.l]:b[x.l]&1?x.r<y.r:x.r>y.r;}
void add(int x)
{
now+=cnt[x];
cnt[x]++;
}
void del(int x)
{
cnt[x]--;
now-=cnt[x];
}
int main()
{
n=read();q=read();t=sqrt(n);
for(int i=1;i<=n;i++) x=read(),x|=(1<<21),a[i]=(a[i-1]^x),b[i]=(i-1)/t+1;
for(int i=1;i<=q;i++)
{
c[i].l=read();c[i].r=read();c[i].id=i;
c[i].l--;
}
sort(c+1,c+q+1,cmp);
for(int i=1;i<=q;i++)
{
A=c[i].l;B=c[i].r;
while(l>A) l--,add(a[l]);
while(r<B) r++,add(a[r]);
while(l<A) del(a[l]),l++;
while(r>B) del(a[r]),r--;
ans[c[i].id]+=1ll*(B-A+1)*(B-A)/2-now;
}
for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3608kb
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: 1ms
memory: 3684kb
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: 2ms
memory: 3712kb
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: 0
Accepted
time: 2ms
memory: 3784kb
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 21
result:
ok 8 numbers
Test #5:
score: 0
Accepted
time: 2ms
memory: 3696kb
input:
10 6 9 539 285 408 615 861 951 413 319 368 4 4 8 10 1 7 3 9 2 3 2 10
output:
1 6 28 28 3 45
result:
ok 6 numbers
Test #6:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
10 6 1348 7002 4687 6325 8253 5750 2464 5509 6543 8704 3 9 4 8 8 8 8 9 2 9 9 10
output:
28 15 1 3 36 3
result:
ok 6 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
10 8 59041 28802 92255 14246 65768 79252 70656 81265 98363 85237 1 6 9 10 4 7 6 8 9 10 1 2 1 3 4 5
output:
21 3 10 6 3 3 6 3
result:
ok 8 numbers
Test #8:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
10 7 28607 249948 373828 584253 989446 308313 199311 253174 283937 133758 2 4 1 2 4 9 7 8 7 8 2 6 1 1
output:
6 3 21 3 3 15 1
result:
ok 7 numbers
Test #9:
score: -100
Wrong Answer
time: 2ms
memory: 3732kb
input:
100 98 6 9 6 10 8 10 3 4 7 5 4 10 2 10 4 5 2 1 7 1 3 1 4 1 1 2 6 9 3 10 2 5 3 2 6 2 1 7 7 6 5 4 2 5 3 2 7 2 6 2 9 7 10 7 4 2 9 3 3 7 9 1 4 9 6 1 5 5 8 3 7 5 8 3 9 5 8 7 8 6 6 3 2 3 8 1 8 1 5 9 1 8 6 3 3 7 10 6 5 5 48 72 14 46 23 28 37 84 1 65 45 72 9 19 9 81 37 53 47 50 25 26 26 88 51 54 53 69 22 94...
output:
316 536 20 1144 2068 395 65 2611 148 10 3 1956 10 146 2611 33 167 6 27 316 604 2977 369 4596 2830 132 1226 53 164 2974 131 3059 798 1496 90 1946 225 65 76 423 335 646 266 1088 907 963 2682 2205 452 149 224 5 3783 1323 102 1229 576 2201 291 677 362 962 1 226 149 723 117 103 3370 911 132 1 90 1143 200...
result:
wrong answer 2nd numbers differ - expected: '534', found: '536'