#include<bits/stdc++.h>
using namespace std;
#define in ({ll x=0;int n=0,c=getchar();for(;!isdigit(c);c=getchar()) n=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
#define inchar ({char c=getchar();while(c==' '||c=='\n') c=getchar();c;})
#define DO for(bool __=1;__;___=0)
#define ll long long
#define FOR(i,a,b) for(int i(a);i<=b;i++)
#define ROF(i,a,b) for(int i(b);a<=i;i--)
#define rr(x) " "<<#x<<'='<<x<<" "
#define bit(x,i) ((x>>(i-1))&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))
#define pow2(x) (1ll<<x)
#define mt make_tuple
#define pi pair<int,int>
#define x first
#define y second
#define VEC(i,a) for(auto&i:a)
#define pb push_back
#define allv(a) a.begin(),a.end()
#define endv(a) (int)a.size()-1
////////////////////////////////////////// NIRO
const int N=1e5+5;
int n,Q;
struct tp
{
int a,b,c,id;
};
tp a[N],a2[N],q[N];
int don,ans[N],finda[N];
bool sortc(tp a,tp b){return a.c<b.c;}
bool sortab(tp u,tp v){return u.a<v.a||(u.a==v.a&&u.b<v.b);}
#define middle(a,b) (a+(b-a)/2)
#define Sfir 1,1,n
#define Snow S,l,r
#define Slef S*2,l,middle(l,r)
#define Srig S*2+1,middle(l,r)+1,r
int s[4*N];
vector<int> ffen[4*N],fen[4*N];
void BUI(int S,int l,int r)
{
// cout<<rr(S) rr(l) rr(r) "\n";
FOR(i,l,r) ffen[S].pb(a[i].b);
sort(allv(ffen[S]));
fen[S].resize(ffen[S].size(),0);
//cout<<rr(S) ":";
//VEC(i,ffen[S]) cout<<i<<" ";cout<<"\n";
if(l==r) return;
BUI(Slef);BUI(Srig);
}
void UPDFEN(int S,int v)
{
//if(S==3&&v==70) cout<<"YES\n\n";
int i=lower_bound(allv(ffen[S]),v)-ffen[S].begin()+1;
for(;i>0;i-=i&-i) fen[S][i-1]++;
}
int GETFEN(int S,int v)
{
int sum=0;
int i=lower_bound(allv(ffen[S]),v)-ffen[S].begin()+1;
for(;i<=fen[S].size();i+=i&-i) sum+=fen[S][i-1];
//cout<<rr(S) rr(v) rr(i) rr(fen[S].size()) rr(sum) "\n";
return sum;
}
void UPD(int S,int l,int r,int x)
{
if(x<l||r<x) return;
//cout<<"update" rr(S) rr(l) rr(r) rr(x) "\n";
UPDFEN(S,a[x].b);
if(l!=r)
UPD(Slef,x),
UPD(Srig,x);
}
int GET(int S,int l,int r,int u,int v,int z)
{
if(v<l||r<u) return 0;
if(u<=l&&r<=v) return GETFEN(S,z);
return GET(Slef,u,v,z)+GET(Srig,u,v,z);
}
int FIND(int x)
{
//cout<<"find" rr(x) " --> ";
int l=1,r=n,res;
while(l<=r)
{
int mid=l+(r-l)/2;
if(x<=a[mid].a) res=mid,r=mid-1;
else l=mid+1;
}
//cout<<rr(res) "\n";
return res;
}
main()
{
//freopen("nr.inp","r",stdin);
n=in,Q=in;
//cout<<rr(n) rr(Q) "\n";
FOR(i,1,n)
{
int x=in,y=in;
a[i]=a2[i]={x,y,x+y,i};
}
FOR(i,1,Q) q[i]={in,in,in,i};
sort(a2+1,a2+n+1,sortc);
sort(q+1,q+Q+1,sortc);
sort(a+1,a+n+1,sortab);
FOR(i,1,n) finda[a[i].id]=i;
//FOR(i,1,n) cout<<rr(i) <<a[i].a<<" "<<a[i].b<<" "<<a[i].c<<"\n";
//FOR(i,1,n) cout<<finda[i]<<" ";cout<<"\n";
BUI(1,1,n);
don=n;
ROF(i,1,Q)
{
//cout<<"=======================" rr(i) rr(q[i].a) rr(q[i].b) rr(q[i].c) "\n";
while(don>1&&q[i].c<=a2[don].c) UPD(Sfir,finda[a2[don].id]),don--;
ans[q[i].id]=GET(Sfir,FIND(q[i].a),n,q[i].b);
// break;
}
FOR(i,1,Q) cout<<ans[i]<<"\n";
}
Compilation message
examination.cpp: In function 'int GETFEN(int, int)':
examination.cpp:74:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;i<=fen[S].size();i+=i&-i) sum+=fen[S][i-1];
~^~~~~~~~~~~~~~~
examination.cpp: At global scope:
examination.cpp:114:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
examination.cpp: In function 'int main()':
examination.cpp:4:128: warning: narrowing conversion of '({...})' from 'long long int' to 'int' inside { } [-Wnarrowing]
#define in ({ll x=0;int n=0,c=getchar();for(;!isdigit(c);c=getchar()) n=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
^
examination.cpp:124:22: note: in expansion of macro 'in'
FOR(i,1,Q) q[i]={in,in,in,i};
^~
examination.cpp:4:128: warning: narrowing conversion of '({...})' from 'long long int' to 'int' inside { } [-Wnarrowing]
#define in ({ll x=0;int n=0,c=getchar();for(;!isdigit(c);c=getchar()) n=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
^
examination.cpp:124:25: note: in expansion of macro 'in'
FOR(i,1,Q) q[i]={in,in,in,i};
^~
examination.cpp:4:128: warning: narrowing conversion of '({...})' from 'long long int' to 'int' inside { } [-Wnarrowing]
#define in ({ll x=0;int n=0,c=getchar();for(;!isdigit(c);c=getchar()) n=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
^
examination.cpp:124:28: note: in expansion of macro 'in'
FOR(i,1,Q) q[i]={in,in,in,i};
^~
examination.cpp: In function 'int FIND(int)':
examination.cpp:111:12: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
return res;
^~~
examination.cpp: In function 'int main()':
examination.cpp:141:25: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
ans[q[i].id]=GET(Sfir,FIND(q[i].a),n,q[i].b);
~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
900 ms |
50196 KB |
Output is correct |
| 2 |
Incorrect |
935 ms |
52208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
900 ms |
50196 KB |
Output is correct |
| 2 |
Incorrect |
935 ms |
52208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
