QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#746717#62. ExaminationShumomo0 1ms10060kbC++141.8kb2024-11-14 15:21:262024-11-14 15:21:26

Judging History

你现在查看的是最新测评结果

  • [2024-11-14 15:21:26]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:10060kb
  • [2024-11-14 15:21:26]
  • 提交

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%