QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#746717 | #62. Examination | Shumomo | 0 | 1ms | 10060kb | C++14 | 1.8kb | 2024-11-14 15:21:26 | 2024-11-14 15:21:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct node{
int a,b,c,d;
bool operator <(const node &aa)const{
return a<aa.a;
}
}x[200009],y[200009];
int n,q,f[200009],ans[200009],v[200009];
void solve(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
solve(l,mid);
solve(mid+1,r);
int nw=r,ll=mid,rr=r;
while(ll>=l&&rr>mid){
if(x[ll].b>x[rr].b){
if(x[ll].d>0){
for(int i=x[ll].c-1;i;i-=(i&(-i)))ans[x[ll].d]+=v[i];
}
y[nw--]=x[ll--];
}
else {
if(x[rr].d<0)for(int i=x[rr].c;i<=n+q;i+=(i&(-i)))v[i]++;
y[nw--]=x[rr--];
}
}
while(ll>=l){
if(x[ll].d>0){
for(int i=x[ll].c-1;i;i-=(i&(-i)))ans[x[ll].d]+=v[i];
}
y[nw--]=x[ll--];
}
while(rr>mid){
if(x[rr].d<0)for(int i=x[rr].c;i<=n+q;i+=(i&(-i)))v[i]++;
y[nw--]=x[rr--];
}
for(int i=mid+1;i<=r;i++){
if(x[i].d<0)for(int j=x[i].c;j<=n+q;j+=(j&(-j)))v[j]--;
}
for(int i=1;i<=n+q;i++)assert(!v[i]);
for(int i=l;i<=r;i++){
x[i]=y[i];
}
return;
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d%d",&x[i].a,&x[i].b);
x[i].c=x[i].a+x[i].b;
x[i].a++;
x[i].b++;
x[i].c++;
x[i].d=-i;
f[i]=x[i].c;
}
for(int i=n+1;i<=n+q;i++){
scanf("%d%d%d",&x[i].a,&x[i].b,&x[i].c);
x[i].d=i-n;
f[i]=x[i].c;
}
sort(f+1,f+n+q+1);
for(int i=1;i<=n+q;i++){
x[i].c=lower_bound(f+1,f+n+q+1,x[i].c)-f;
x[i].c=n+q+1-x[i].c;
}
sort(x+1,x+n+q+1);
solve(1,n+q);
for(int i=1;i<=q;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: 2
Accepted
time: 0ms
memory: 8008kb
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:
1 0 2 0 1 1 0 1 3 1
result:
ok 10 lines
Test #2:
score: 2
Accepted
time: 1ms
memory: 10060kb
input:
10 10 6 67 36 99 13 45 100 87 60 72 55 41 62 92 55 39 90 22 0 99 34 89 79 17 17 23 60 26 171 29 88 190 32 71 98 20 29 192 50 7 34 14 21 139 54 35 103 86 91 1
output:
2 7 1 0 4 0 6 2 3 0
result:
ok 10 lines
Test #3:
score: 0
Wrong Answer
time: 1ms
memory: 7872kb
input:
10 10 67 72 94 99 34 22 1 71 68 18 90 94 29 44 98 61 46 9 94 76 73 36 11 30 26 75 5 85 112 38 35 111 39 72 143 6 64 130 31 24 134 82 86 188 80 20 151 91 32 62
output:
4 5 2 5 3 4 5 1 4 4
result:
wrong answer 10th lines differ - expected: '3', found: '4'
Subtask #2:
score: 0
Time Limit Exceeded
Test #19:
score: 0
Time Limit Exceeded
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:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%