#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int> >, rb_tree_tag,tree_order_statistics_node_update>
#define forw(i,a,b) for(ll i=a;i<=b;i++)
#define forb(i,a,b) for(ll i=a;i>=b;i--)
#define fi first
#define se second
#define pb push_back
#define pu push
#define all(a) a.begin(),a.end()
#define getbit(mask,i) ((mask>>(i))&1)
#define minimize(a,b) (a)=min((a),(b))
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll maxN=1e5+5;
const ll mod=1e9+9;
const ll oo=1e18+1;
const int tx[4]={-1,1,0,0};
const int ty[4]={0,0,-1,1};
const int len=350;
struct fenwick
{
vector <int> fen;
int n;
fenwick(int _n=1e5)
{
n=_n;
fen.assign(n+5,0);
}
void update(int pos)
{
for(;pos>0;pos-=pos&-pos) fen[pos]++;
return;
}
int get(int pos)
{
if (!pos) return 0;
int ans=0;
for(;pos<=n;pos+=pos&-pos) ans+=fen[pos];
return ans;
}
}fen[len+3];
struct dataa
{
int x,y,z,id;
};
dataa a[maxN],query[maxN];
ordered_set save[maxN];
int n,q,ans[maxN];
vector <int> pend_x,pend_y;
bool cmp(dataa &a, dataa &b)
{
return a.z>b.z;
}
void solve()
{
cin>>n>>q;
forw(i,1,n)
{
cin>>a[i].x>>a[i].y;
a[i].z=a[i].x+a[i].y;
pend_x.pb(a[i].x);
pend_y.pb(a[i].y);
}
sort(a+1,a+1+n,cmp);
sort(all(pend_x)); pend_x.resize(unique(all(pend_x))-pend_x.begin());
sort(all(pend_y)); pend_y.resize(unique(all(pend_y))-pend_y.begin());
forw(i,1,q)
{
cin>>query[i].x>>query[i].y>>query[i].z;
query[i].id=i;
}
sort(query+1,query+1+q,cmp);
int idx=1;
forw(i,1,n)
{
int pos1=lower_bound(all(pend_x),a[i].x)-pend_x.begin()+1;
int pos2=lower_bound(all(pend_y),a[i].y)-pend_y.begin()+1;
// update ele
save[pos1].insert({pos2,i});
// update block
pos1=(pos1-1)/len;
fen[pos1].update(pos2);
//cout<<"update: "<<pos1<<" "<<pos2<<" "<<a[i].x<<" "<<a[i].y<<" "<<a[i].z<<endl;
if (i<n && a[i].z==a[i+1].z) continue;
while (idx<=q && (i==n || a[i+1].z<query[idx].z))
{
if (a[i].z<query[idx].z)
{
idx++;
continue;
}
int cnt=0;
pos1=lower_bound(all(pend_x),query[idx].x)-pend_x.begin()+1;
pos2=lower_bound(all(pend_y),query[idx].y)-pend_y.begin()+1;
int L=(pos1-1)/len;
int R=(pend_x.size()-1)/len;
// get block
forw(block,L+1,R)
cnt+=fen[block].get(pos2);
// get ele
forw(ele,pos1,(L+1)*len)
cnt+=save[ele].size()-save[ele].order_of_key({pos2,0});
ans[query[idx].id]=cnt;
idx++;
}
}
forw(i,1,q) cout<<ans[i]<<"\n";
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("bruh.inp","r",stdin);
//freopen("bruh.out","w",stdout);
int t=1; //cin>>t;
while (t--) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
148380 KB |
Output is correct |
2 |
Correct |
64 ms |
148364 KB |
Output is correct |
3 |
Correct |
61 ms |
148316 KB |
Output is correct |
4 |
Correct |
64 ms |
148300 KB |
Output is correct |
5 |
Correct |
63 ms |
148280 KB |
Output is correct |
6 |
Correct |
61 ms |
148380 KB |
Output is correct |
7 |
Correct |
68 ms |
148852 KB |
Output is correct |
8 |
Correct |
67 ms |
148812 KB |
Output is correct |
9 |
Correct |
67 ms |
148812 KB |
Output is correct |
10 |
Correct |
66 ms |
148736 KB |
Output is correct |
11 |
Correct |
67 ms |
148824 KB |
Output is correct |
12 |
Correct |
68 ms |
148736 KB |
Output is correct |
13 |
Correct |
68 ms |
148840 KB |
Output is correct |
14 |
Correct |
69 ms |
148844 KB |
Output is correct |
15 |
Correct |
70 ms |
148808 KB |
Output is correct |
16 |
Correct |
66 ms |
148812 KB |
Output is correct |
17 |
Correct |
65 ms |
148772 KB |
Output is correct |
18 |
Correct |
64 ms |
148644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1487 ms |
160792 KB |
Output is correct |
2 |
Correct |
1458 ms |
160860 KB |
Output is correct |
3 |
Correct |
1497 ms |
161120 KB |
Output is correct |
4 |
Correct |
1004 ms |
160888 KB |
Output is correct |
5 |
Correct |
381 ms |
160860 KB |
Output is correct |
6 |
Correct |
319 ms |
160520 KB |
Output is correct |
7 |
Correct |
1764 ms |
161040 KB |
Output is correct |
8 |
Correct |
1278 ms |
160844 KB |
Output is correct |
9 |
Correct |
1532 ms |
161036 KB |
Output is correct |
10 |
Correct |
259 ms |
160668 KB |
Output is correct |
11 |
Correct |
832 ms |
160740 KB |
Output is correct |
12 |
Correct |
246 ms |
160028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1487 ms |
160792 KB |
Output is correct |
2 |
Correct |
1458 ms |
160860 KB |
Output is correct |
3 |
Correct |
1497 ms |
161120 KB |
Output is correct |
4 |
Correct |
1004 ms |
160888 KB |
Output is correct |
5 |
Correct |
381 ms |
160860 KB |
Output is correct |
6 |
Correct |
319 ms |
160520 KB |
Output is correct |
7 |
Correct |
1764 ms |
161040 KB |
Output is correct |
8 |
Correct |
1278 ms |
160844 KB |
Output is correct |
9 |
Correct |
1532 ms |
161036 KB |
Output is correct |
10 |
Correct |
259 ms |
160668 KB |
Output is correct |
11 |
Correct |
832 ms |
160740 KB |
Output is correct |
12 |
Correct |
246 ms |
160028 KB |
Output is correct |
13 |
Correct |
1252 ms |
162404 KB |
Output is correct |
14 |
Correct |
1554 ms |
162328 KB |
Output is correct |
15 |
Correct |
1647 ms |
162048 KB |
Output is correct |
16 |
Correct |
1046 ms |
161528 KB |
Output is correct |
17 |
Correct |
350 ms |
161592 KB |
Output is correct |
18 |
Correct |
304 ms |
160536 KB |
Output is correct |
19 |
Correct |
1242 ms |
162624 KB |
Output is correct |
20 |
Correct |
1322 ms |
162436 KB |
Output is correct |
21 |
Correct |
1389 ms |
162416 KB |
Output is correct |
22 |
Correct |
248 ms |
161084 KB |
Output is correct |
23 |
Correct |
902 ms |
161168 KB |
Output is correct |
24 |
Correct |
258 ms |
160112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
148380 KB |
Output is correct |
2 |
Correct |
64 ms |
148364 KB |
Output is correct |
3 |
Correct |
61 ms |
148316 KB |
Output is correct |
4 |
Correct |
64 ms |
148300 KB |
Output is correct |
5 |
Correct |
63 ms |
148280 KB |
Output is correct |
6 |
Correct |
61 ms |
148380 KB |
Output is correct |
7 |
Correct |
68 ms |
148852 KB |
Output is correct |
8 |
Correct |
67 ms |
148812 KB |
Output is correct |
9 |
Correct |
67 ms |
148812 KB |
Output is correct |
10 |
Correct |
66 ms |
148736 KB |
Output is correct |
11 |
Correct |
67 ms |
148824 KB |
Output is correct |
12 |
Correct |
68 ms |
148736 KB |
Output is correct |
13 |
Correct |
68 ms |
148840 KB |
Output is correct |
14 |
Correct |
69 ms |
148844 KB |
Output is correct |
15 |
Correct |
70 ms |
148808 KB |
Output is correct |
16 |
Correct |
66 ms |
148812 KB |
Output is correct |
17 |
Correct |
65 ms |
148772 KB |
Output is correct |
18 |
Correct |
64 ms |
148644 KB |
Output is correct |
19 |
Correct |
1487 ms |
160792 KB |
Output is correct |
20 |
Correct |
1458 ms |
160860 KB |
Output is correct |
21 |
Correct |
1497 ms |
161120 KB |
Output is correct |
22 |
Correct |
1004 ms |
160888 KB |
Output is correct |
23 |
Correct |
381 ms |
160860 KB |
Output is correct |
24 |
Correct |
319 ms |
160520 KB |
Output is correct |
25 |
Correct |
1764 ms |
161040 KB |
Output is correct |
26 |
Correct |
1278 ms |
160844 KB |
Output is correct |
27 |
Correct |
1532 ms |
161036 KB |
Output is correct |
28 |
Correct |
259 ms |
160668 KB |
Output is correct |
29 |
Correct |
832 ms |
160740 KB |
Output is correct |
30 |
Correct |
246 ms |
160028 KB |
Output is correct |
31 |
Correct |
1252 ms |
162404 KB |
Output is correct |
32 |
Correct |
1554 ms |
162328 KB |
Output is correct |
33 |
Correct |
1647 ms |
162048 KB |
Output is correct |
34 |
Correct |
1046 ms |
161528 KB |
Output is correct |
35 |
Correct |
350 ms |
161592 KB |
Output is correct |
36 |
Correct |
304 ms |
160536 KB |
Output is correct |
37 |
Correct |
1242 ms |
162624 KB |
Output is correct |
38 |
Correct |
1322 ms |
162436 KB |
Output is correct |
39 |
Correct |
1389 ms |
162416 KB |
Output is correct |
40 |
Correct |
248 ms |
161084 KB |
Output is correct |
41 |
Correct |
902 ms |
161168 KB |
Output is correct |
42 |
Correct |
258 ms |
160112 KB |
Output is correct |
43 |
Runtime error |
287 ms |
313860 KB |
Execution killed with signal 11 |
44 |
Halted |
0 ms |
0 KB |
- |