QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#812093 | #62. Examination | guleng2007# | 0 | 140ms | 12352kb | C++23 | 1.5kb | 2024-12-13 11:27:49 | 2024-12-13 11:27:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct node
{
int a, b, c, op;
} q[N], a[N];
int c[N], ans[N], num[N], cnt;
bool cmp(node a,node b)
{
if(a.a!=b.a)
return a.a>b.a;
if(a.b!=b.b)
return a.b>b.b;
if(a.c!=b.c)
return a.c>b.c;
return a.op<b.op;
}
void update(int x,int y)
{
for(int i=x;i;i-=i&-i)
c[i] += y;
}
int query(int x)
{
int ans=0;
for(int i=x;i<=cnt;i+=i&-i)
ans += c[i];
return ans;
}
void CDQ(int l,int r)
{
if(l==r)
return;
int mid=(l+r)/2;
CDQ(l,mid);
CDQ(mid+1,r);
int cur1=l, cur2=mid+1, cur=l;
while(cur1<=mid || cur2<=r)
{
if(cur2>r || (cur1<=mid && q[cur1].b>=q[cur2].b))
{
if(q[cur1].op==0)
update(q[cur1].c,1);
a[cur++]=q[cur1++];
}
else
{
if(q[cur2].op)
ans[q[cur2].op] += query(q[cur2].c);
a[cur++]=q[cur2++];
}
}
for(int i=l;i<=r;i++)
q[i]=a[i];
for(int i=l;i<=mid;i++)
if(q[i].op==0)
update(q[i].c,-1);
}
int main()
{
int n, m;
cin >> n >> m;
for(int i=1;i<=n;i++)
{
scanf("%d %d",&q[i].a,&q[i].b);
q[i].c=q[i].a+q[i].b;
q[i].op=0;
}
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&q[i+n].a,&q[i+n].b,&q[i+n].c);
q[i+n].op=i;
}
for(int i=1;i<=n+m;i++)
num[++cnt]=q[i].c;
sort(num+1,num+cnt+1);
cnt=unique(num+1,num+cnt+1)-num-1;
for(int i=1;i<=n+m;i++)
q[i].c=lower_bound(num+1,num+cnt+1,q[i].c)-num;
sort(q+1,q+n+m+1,cmp);
CDQ(1,n+m);
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 10020kb
input:
10 10 28 2 78 81 39 79 61 31 36 99 90 5 20 55 91 4 48 19 80 7 52 43 78 64 65 171 34 68 124 37 80 161 53 19 123 49 58 109 95 46 30 45 48 60 47 13 54 64 30 144
output:
-2 0 -8 0 -3 -5 0 -1 2 -3
result:
wrong answer 1st lines differ - expected: '1', found: '-2'
Subtask #2:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 140ms
memory: 12352kb
input:
100000 100000 26753 11234 32815 62591 34318 93262 77179 57605 88208 33327 48449 99060 42403 58561 85715 7001 2418 90938 77409 6957 546 83283 53957 8374 49470 1483 65866 64950 4269 8745 19041 85833 22344 90706 92926 35603 54697 75311 72601 66401 77598 8193 3751 54202 32710 5877 23835 38264 34381 3338...
output:
3653 15966 23790 15538 14595 27036 6072 30862 30067 25519 19361 10384 30042 217 18506 3524 1976 18295 39435 19228 69121 26191 13796 9127 18425 1135 13489 21335 16021 74125 30297 69775 45636 56523 1039 58483 8623 3333 3199 6308 9663 39612 40495 7959 42857 11111 26691 20517 75503 28392 4292 28300 6590...
result:
wrong answer 1st lines differ - expected: '3392', found: '3653'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%