#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
using namespace std;
const int N=1e5+5;
int n,m,T,k,a[N],b[N],x[N],y[N],z[N],ans[N];
vector<int> t[N*4];
void build(int v, int tl, int tr) {
if (tl==tr) {
t[v].pb(a[tl]+b[tl]); return;
}
int mid=(tl+tr)/2;
build(v*2,tl,mid); build(v*2+1,mid+1,tr);
merge(all(t[v*2]),all(t[v*2+1]),back_inserter(t[v]));
}
void update(int v, int tl, int tr, int ind, int val) {
t[v].clear();
if (tl==tr) {
t[v].pb(val); return;
}
int mid=(tl+tr)/2;
if (ind<=mid) update(v*2,tl,mid,ind,val);
else update(v*2+1,mid+1,tr,ind,val);
merge(all(t[v*2]),all(t[v*2+1]),back_inserter(t[v]));
}
int query(int v, int tl, int tr, int l, int r, int val) {
if (l>r) return 0;
if (tl==l && tr==r) {
auto it=lower_bound(all(t[v]),val);
int num=it-t[v].begin(); num=(tr-tl+1)-num;
return num;
}
int mid=(tl+tr)/2;
return query(v*2,tl,mid,l,min(r,mid),val)+query(v*2+1,mid+1,tr,max(l,mid+1),r,val);
}
void test_case() {
cin>>n>>m;
pii ab[n+1];
for (int i=1; i<=n; i++) cin>>ab[i].f>>ab[i].s;
sort(ab+1,ab+1+n);
for (int i=1; i<=n; i++) {
a[i]=ab[i].f; b[i]=ab[i].s;
}
for (int i=1; i<=m; i++) cin>>x[i]>>y[i]>>z[i];
pii bi[n+1],yi[m+1];
for (int i=1; i<=n; i++) {
bi[i]={b[i],i};
}
for (int i=1; i<=m; i++) {
yi[i]={y[i],i};
}
sort(bi+1,bi+1+n); sort(yi+1,yi+1+m);
int cur=1;
build(1,1,n);
for (int i=1; i<=m; i++) {
int ind=yi[i].s;
while (cur<=n && bi[cur].f<yi[i].f) {
update(1,1,n,bi[cur].s,0); cur++;
}
int l=1,r=n,idx=0;
while (l<=r) {
int mid=(l+r)/2;
if (a[mid]>=x[ind]) {
idx=mid; r=mid-1;
}
else {
l=mid+1;
}
}
ans[ind]=query(1,1,n,idx,n,z[ind]);
}
for (int i=1; i<=m; i++) cout<<ans[i]<<endl;
}
main () {
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
T=1;
while (T--) test_case();
}
Compilation message
examination.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
1 | #pragma gcc diagnostic "-std=c++1z"
|
examination.cpp:80:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
80 | main () {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
517 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3059 ms |
30196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3059 ms |
30196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
517 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
