#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<pair<int,int>,null_type,greater<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int n,q,cate;
pair<int,int> a[100005];
int rez[100005];
pair<pair<int,pair<int,int>>,int> qrys[100005];
map<int,int> mp;
map<int,int> nrm;
bool cmp(pair<int,int> x, pair<int,int> y)
{
return x.first + x.second > y.first + y.second;
}
ordered_set aint[530000];
void upd(int nod, int st, int dr, int poz, pair<int,int> newv)
{
aint[nod].insert(newv);
if(st==dr)
return;
int mij=(st+dr)/2;
if(poz<=mij) upd(nod*2,st,mij,poz,newv);
else upd(nod*2+1,mij+1,dr,poz,newv);
}
int qry(int nod, int st, int dr, int le, int ri, int lim)
{
if(le>ri)
return 0;
if(le==st && dr==ri)
return aint[nod].order_of_key({lim,-1});
int mij=(st+dr)/2;
return qry(nod*2,st,mij,le,min(mij,ri),lim) + qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,lim);
}
signed main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i].first>>a[i].second;
mp[a[i].first]++;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=q;i++)
{
cin>>qrys[i].first.second.first>>qrys[i].first.second.second>>qrys[i].first.first;
qrys[i].second=i;
mp[qrys[i].first.second.first]++;
}
for(auto it:mp)
nrm[it.first]=++cate;
sort(qrys+1,qrys+1+q);
int poz=1;
for(int i=q;i>0;i--)
{
while(poz<=n && a[poz].first+a[poz].second >= qrys[i].first.first)
{
///adauga poz
upd(1,1,cate,nrm[a[poz].first],{a[poz].second,poz});
poz++;
}
rez[qrys[i].second] = qry(1,1,cate,nrm[qrys[i].first.second.first],cate,qrys[i].first.second.second);
}
for(int i=1;i<=q;i++)
cout<<rez[i]<<"\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
52060 KB |
Output is correct |
2 |
Correct |
33 ms |
52048 KB |
Output is correct |
3 |
Correct |
32 ms |
52060 KB |
Output is correct |
4 |
Correct |
32 ms |
52048 KB |
Output is correct |
5 |
Correct |
37 ms |
52264 KB |
Output is correct |
6 |
Correct |
32 ms |
52060 KB |
Output is correct |
7 |
Correct |
54 ms |
55124 KB |
Output is correct |
8 |
Correct |
54 ms |
55384 KB |
Output is correct |
9 |
Correct |
55 ms |
55376 KB |
Output is correct |
10 |
Correct |
53 ms |
55288 KB |
Output is correct |
11 |
Correct |
42 ms |
53072 KB |
Output is correct |
12 |
Correct |
40 ms |
53076 KB |
Output is correct |
13 |
Correct |
54 ms |
55376 KB |
Output is correct |
14 |
Correct |
53 ms |
55380 KB |
Output is correct |
15 |
Correct |
52 ms |
55376 KB |
Output is correct |
16 |
Correct |
42 ms |
52820 KB |
Output is correct |
17 |
Correct |
51 ms |
55376 KB |
Output is correct |
18 |
Correct |
38 ms |
52756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1732 ms |
171080 KB |
Output is correct |
2 |
Correct |
1765 ms |
171044 KB |
Output is correct |
3 |
Correct |
1738 ms |
171132 KB |
Output is correct |
4 |
Correct |
935 ms |
171348 KB |
Output is correct |
5 |
Correct |
363 ms |
81796 KB |
Output is correct |
6 |
Correct |
318 ms |
81752 KB |
Output is correct |
7 |
Correct |
1670 ms |
166448 KB |
Output is correct |
8 |
Correct |
1756 ms |
171160 KB |
Output is correct |
9 |
Correct |
1514 ms |
166376 KB |
Output is correct |
10 |
Correct |
193 ms |
65956 KB |
Output is correct |
11 |
Correct |
864 ms |
171124 KB |
Output is correct |
12 |
Correct |
375 ms |
71844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1732 ms |
171080 KB |
Output is correct |
2 |
Correct |
1765 ms |
171044 KB |
Output is correct |
3 |
Correct |
1738 ms |
171132 KB |
Output is correct |
4 |
Correct |
935 ms |
171348 KB |
Output is correct |
5 |
Correct |
363 ms |
81796 KB |
Output is correct |
6 |
Correct |
318 ms |
81752 KB |
Output is correct |
7 |
Correct |
1670 ms |
166448 KB |
Output is correct |
8 |
Correct |
1756 ms |
171160 KB |
Output is correct |
9 |
Correct |
1514 ms |
166376 KB |
Output is correct |
10 |
Correct |
193 ms |
65956 KB |
Output is correct |
11 |
Correct |
864 ms |
171124 KB |
Output is correct |
12 |
Correct |
375 ms |
71844 KB |
Output is correct |
13 |
Correct |
2459 ms |
171048 KB |
Output is correct |
14 |
Correct |
2880 ms |
171012 KB |
Output is correct |
15 |
Correct |
2019 ms |
171080 KB |
Output is correct |
16 |
Correct |
1359 ms |
171156 KB |
Output is correct |
17 |
Correct |
438 ms |
81856 KB |
Output is correct |
18 |
Correct |
347 ms |
81876 KB |
Output is correct |
19 |
Correct |
2506 ms |
170872 KB |
Output is correct |
20 |
Correct |
2363 ms |
171280 KB |
Output is correct |
21 |
Correct |
1873 ms |
169484 KB |
Output is correct |
22 |
Correct |
184 ms |
65728 KB |
Output is correct |
23 |
Correct |
878 ms |
170944 KB |
Output is correct |
24 |
Correct |
370 ms |
71936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
52060 KB |
Output is correct |
2 |
Correct |
33 ms |
52048 KB |
Output is correct |
3 |
Correct |
32 ms |
52060 KB |
Output is correct |
4 |
Correct |
32 ms |
52048 KB |
Output is correct |
5 |
Correct |
37 ms |
52264 KB |
Output is correct |
6 |
Correct |
32 ms |
52060 KB |
Output is correct |
7 |
Correct |
54 ms |
55124 KB |
Output is correct |
8 |
Correct |
54 ms |
55384 KB |
Output is correct |
9 |
Correct |
55 ms |
55376 KB |
Output is correct |
10 |
Correct |
53 ms |
55288 KB |
Output is correct |
11 |
Correct |
42 ms |
53072 KB |
Output is correct |
12 |
Correct |
40 ms |
53076 KB |
Output is correct |
13 |
Correct |
54 ms |
55376 KB |
Output is correct |
14 |
Correct |
53 ms |
55380 KB |
Output is correct |
15 |
Correct |
52 ms |
55376 KB |
Output is correct |
16 |
Correct |
42 ms |
52820 KB |
Output is correct |
17 |
Correct |
51 ms |
55376 KB |
Output is correct |
18 |
Correct |
38 ms |
52756 KB |
Output is correct |
19 |
Correct |
1732 ms |
171080 KB |
Output is correct |
20 |
Correct |
1765 ms |
171044 KB |
Output is correct |
21 |
Correct |
1738 ms |
171132 KB |
Output is correct |
22 |
Correct |
935 ms |
171348 KB |
Output is correct |
23 |
Correct |
363 ms |
81796 KB |
Output is correct |
24 |
Correct |
318 ms |
81752 KB |
Output is correct |
25 |
Correct |
1670 ms |
166448 KB |
Output is correct |
26 |
Correct |
1756 ms |
171160 KB |
Output is correct |
27 |
Correct |
1514 ms |
166376 KB |
Output is correct |
28 |
Correct |
193 ms |
65956 KB |
Output is correct |
29 |
Correct |
864 ms |
171124 KB |
Output is correct |
30 |
Correct |
375 ms |
71844 KB |
Output is correct |
31 |
Correct |
2459 ms |
171048 KB |
Output is correct |
32 |
Correct |
2880 ms |
171012 KB |
Output is correct |
33 |
Correct |
2019 ms |
171080 KB |
Output is correct |
34 |
Correct |
1359 ms |
171156 KB |
Output is correct |
35 |
Correct |
438 ms |
81856 KB |
Output is correct |
36 |
Correct |
347 ms |
81876 KB |
Output is correct |
37 |
Correct |
2506 ms |
170872 KB |
Output is correct |
38 |
Correct |
2363 ms |
171280 KB |
Output is correct |
39 |
Correct |
1873 ms |
169484 KB |
Output is correct |
40 |
Correct |
184 ms |
65728 KB |
Output is correct |
41 |
Correct |
878 ms |
170944 KB |
Output is correct |
42 |
Correct |
370 ms |
71936 KB |
Output is correct |
43 |
Correct |
2594 ms |
189316 KB |
Output is correct |
44 |
Correct |
2336 ms |
194188 KB |
Output is correct |
45 |
Correct |
2849 ms |
194412 KB |
Output is correct |
46 |
Correct |
1401 ms |
192812 KB |
Output is correct |
47 |
Correct |
405 ms |
85268 KB |
Output is correct |
48 |
Correct |
312 ms |
82772 KB |
Output is correct |
49 |
Correct |
2339 ms |
194104 KB |
Output is correct |
50 |
Correct |
2559 ms |
194112 KB |
Output is correct |
51 |
Correct |
2376 ms |
194012 KB |
Output is correct |
52 |
Correct |
370 ms |
68916 KB |
Output is correct |
53 |
Correct |
1010 ms |
191528 KB |
Output is correct |