QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#80217#62. Examinationlmeowdn0 174ms19576kbC++142.5kb2023-02-23 09:22:232023-02-23 09:22:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-23 09:22:26]
  • 评测
  • 测评结果:0
  • 用时:174ms
  • 内存:19576kb
  • [2023-02-23 09:22:23]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
#define sgn(x) ((x)&1?-1:1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

int read() {
    int x=0,w=1; char c=getchar(); 
    while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
    while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
    return x*w;
}

const int N=1e5+9,lim=1e9;

int n,m,s[N],t[N],a[N],b[N],c[N],ans[N];
struct node {int id,tp,x,y;} f[N<<1];
bool cmp(const node &a,const node &b) {return a.x==b.x?(a.tp<b.tp):(a.x>b.x);}

namespace SegT {
    int ls[N<<5],rs[N<<5],tot=1,s[N<<1],rt=1;
    void init() {
        rep(i,1,tot) ls[i]=rs[i]=s[i]=0;
        tot=rt=1;
    }
    void insert(int &p,int l,int r,int x) {
        if(!p) p=++tot; s[p]++; if(l==r) return; int mid=l+r>>1;
        if(x<=mid) insert(ls[p],l,mid,x); else insert(rs[p],mid+1,r,x);
    }
    int leq(int p,int l,int r,int x) {
        if(!p) return 0; if(l==r) return s[p]; int mid=l+r>>1;
        if(x<=mid) return leq(ls[p],l,mid,x); else return s[ls[p]]+leq(rs[p],mid+1,r,x);
    }
    int geq(int p,int l,int r,int x) {
        if(!p) return 0; if(l==r) return s[p]; int mid=l+r>>1;
        if(x<=mid) return s[rs[p]]+geq(ls[p],l,mid,x); else return geq(rs[p],mid+1,r,x);
    }
}

void work() {
    SegT::init();
    sort(f+1,f+n+m+1,cmp);
    rep(i,1,n+m) {
        if(f[i].tp==0) SegT::insert(SegT::rt,0,lim,f[i].y);
        else if(f[i].tp==1) ans[f[i].id]+=SegT::geq(SegT::rt,0,lim,f[i].y);
        else if(f[i].tp==2) ans[f[i].id]+=SegT::leq(SegT::rt,0,lim,f[i].y);
        else if(f[i].tp==3) ans[f[i].id]-=SegT::leq(SegT::rt,0,lim,f[i].y);
        else assert(0);
    }
}

signed main() {
    n=read(), m=read();
    rep(i,1,n) s[i]=read(), t[i]=read();
    rep(i,1,m) a[i]=read(), b[i]=read(), c[i]=max(read(),a[i]+b[i]);
    rep(i,1,n) f[i]=(node){i,0,s[i],s[i]+t[i]};
    rep(i,1,m) f[i+n]=(node){i,1,a[i],c[i]};
    work();
    rep(i,1,n) f[i]=(node){i,0,s[i],s[i]+t[i]};
    rep(i,1,m) f[i+n]=(node){i,2,c[i]-b[i]+1,c[i]-1};
    work();
    rep(i,1,n) f[i]=(node){i,0,s[i],t[i]};
    rep(i,1,m) f[i+n]=(node){i,3,c[i]-b[i]+1,b[i]-1};
    work();
    rep(i,1,m) printf("%lld\n",ans[i]);
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 2
Accepted
time: 1ms
memory: 3596kb

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: 0
Accepted
time: 2ms
memory: 3596kb

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
Accepted
time: 2ms
memory: 3600kb

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
3

result:

ok 10 lines

Test #4:

score: -2
Wrong Answer
time: 2ms
memory: 3608kb

input:

10 10
667489048 282547819
694873877 525794923
605957229 147658688
928289876 455560133
465507205 531350815
397977066 913356070
351069660 834164613
611261253 238522918
683770744 737447844
351350094 473152918
514777487 599392520 569824365
137189600 455145855 1628925058
608994260 433029864 1934471803
80...

output:

4
5
3
1
6
1
10
5
1
1

result:

wrong answer 1st lines differ - expected: '1', found: '4'

Subtask #2:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 174ms
memory: 19576kb

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:

3392
12465
20237
13565
11736
1182147
4108
33065
27851
26019
23511
12295
30617
229
20830
1461
3465
17020
36047
23196
1222712
24530
13442
8259
24433
733
10411
20119
15897
1154920
27339
1149671
46246
61350
520
59415
6149
798
2836
4628
14774
1125133
38231
7313
39010
14774
27553
20182
82757
35655
3811
29...

result:

wrong answer 6th lines differ - expected: '28514', found: '1182147'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%