#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;
static char stdinBuffer[1024];
static char* stdinDataEnd = stdinBuffer + sizeof (stdinBuffer);
static const char* stdinPos = stdinDataEnd;
void readAhead(size_t amount)
{
size_t remaining = stdinDataEnd - stdinPos;
if (remaining < amount) {
memmove(stdinBuffer, stdinPos, remaining);
size_t sz = fread(stdinBuffer + remaining, 1, sizeof (stdinBuffer) - remaining, stdin);
stdinPos = stdinBuffer;
stdinDataEnd = stdinBuffer + remaining + sz;
if (stdinDataEnd != stdinBuffer + sizeof (stdinBuffer))
*stdinDataEnd = 0;
}
}
int read_int()
{
readAhead(16);
int x = 0;
bool neg = false;
if (*stdinPos == '-') {
++stdinPos;
neg = true;
}
while (*stdinPos >= '0' && *stdinPos <= '9') {
x *= 10;
x += *stdinPos - '0';
++stdinPos;
}
return neg ? -x : x;
}
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]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
37880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
137 ms |
45296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
137 ms |
45296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
37880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
