#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;
typedef tree<
pair<int,int>,
null_type,
less<pair<int,int> >,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
const int N=1e5+5;
int readInt () {
bool minus = false;
int result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = (result<<3)+(result<<1) + (ch - '0');
}
if (minus)
return -result;
else
return result;
}
ordered_set btree[4*N];
pair<int,int> arr[N];
pair<pair<int,int>, pair<int,int> > qs[N];
vector<int> cmp;
int ans[N];
int n,q;
int get(int x)
{
return lower_bound(cmp.begin(),cmp.end(),x)-cmp.begin();
}
void add(int ind,int sm,int x,int node=1,int l=0,int r=cmp.size()-1)
{
if(r<ind||l>ind) return;
btree[node].insert({sm,x});
if(l==r)
return;
int mid=(l+r)/2;
add(ind,sm,x,node<<1,l,mid);
add(ind,sm,x,(node<<1)+1,mid+1,r);
}
void rem(int ind,int sm,int x,int node=1,int l=0,int r=cmp.size()-1)
{
if(r<ind||l>ind) return;
btree[node].erase({sm,x});
if(l==r)
return;
int mid=(l+r)/2;
rem(ind,sm,x,node<<1,l,mid);
rem(ind,sm,x,(node<<1)+1,mid+1,r);
}
int query(int ql,int qr,int val,int node=1,int l=0,int r=cmp.size()-1)
{
if(r<ql||qr<l) return 0;
if(ql<=l&&r<=qr)
{
return btree[node].size()-btree[node].order_of_key({val,-1});
}
int mid=(l+r)/2;
return query(ql,qr,val,node<<1,l,mid)+query(ql,qr,val,(node<<1)+1,mid+1,r);
}
int main()
{
//scanf("%d %d",&n,&q);
n=read_int(); q=read_int();
for(int i=0;i<n;i++)
{
arr[i].F=read_int(); arr[i].S=read_int();
//scanf("%d %d",&arr[i].F,&arr[i].S);
cmp.push_back(arr[i].S);
}
for(int i=0;i<q;i++)
{
//scanf("%d %d %d",&qs[i].F.F,&qs[i].F.S,&qs[i].S.F);
qs[i].F.F=read_int(); qs[i].F.S=read_int();
qs[i].S.F=read_int();
qs[i].S.S=i;
cmp.push_back(qs[i].F.S);
}
sort(cmp.begin(),cmp.end());
cmp.erase(unique(cmp.begin(),cmp.end()),cmp.end());
sort(arr,arr+n);
sort(qs,qs+q);
for(int i=0;i<n;i++)
{
add(get(arr[i].S),arr[i].F+arr[i].S,i);
}
int curs=0;
for(int i=0;i<q;i++)
{
while(arr[curs].F<qs[i].F.F)
{
rem(get(arr[curs].S),arr[curs].F+arr[curs].S,curs);
curs++;
}
/*cout << "ON " << qs[i].F.F << " " << curs << endl;
for(int i=0;i<btree[1].size();i++)
{
auto x=*btree[1].find_by_order(i);
cout << x.F << " " << x.S << endl;
}*/
ans[qs[i].S.S]=query(get(qs[i].F.S),cmp.size()-1,qs[i].S.F);
}
for(int i=0;i<q;i++)
printf("%d\n",ans[i]);
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:92:4: error: 'read_int' was not declared in this scope
n=read_int(); q=read_int();
^~~~~~~~
examination.cpp:92:4: note: suggested alternative: 'readInt'
n=read_int(); q=read_int();
^~~~~~~~
readInt
