//八(＾□＾*)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=3e5+6;
const ll SQRT=600;
ll n,q;
ll ans[MAXN];
set<pair<ll,ll> >xs;
set<ll>ys,zs;
ll s[MAXN],t[MAXN],sum[MAXN];
ll x[MAXN],y[MAXN],z[MAXN];
map<pair<ll,ll>,ll>newx;
map<ll,ll>newy,newz;
struct student
{
ll a,b,c;
student(){}
student(ll _a,ll _b,ll _c)
{
a=_a;b=_b;c=_c;
}
bool operator<(student const& other)const
{
return b<other.b;
}
};
struct query
{
ll a,b,c,pos;
query(){}
query(ll _a,ll _b,ll _c,ll _pos)
{
a=_a;b=_b;c=_c;pos=_pos;
}
bool operator<(query const& other)const
{
return b<other.b;
}
};
vector<student>blocks1[SQRT];
vector<query>blocks2[SQRT];
ll BIT[MAXN];
void update(ll idx,ll val)
{
++idx;
for(;idx<MAXN;idx+=idx&(-idx))
{
BIT[idx]+=val;
}
}
ll query(ll idx)
{
++idx;
ll ret=0;
for(;idx>0;idx-=idx&(-idx))
{
ret+=BIT[idx];
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>q;
for(ll i=1;i<=n;++i)
{
cin>>s[i]>>t[i];
xs.insert({s[i],i});
sum[i]=s[i]+t[i];
ys.insert(t[i]);zs.insert(sum[i]);
}
ll cntx=0,cnty=0,cntz=0;
for(auto xd:xs)
{
newx[xd]=++cntx;
}
for(auto xd:ys)
{
newy[xd]=++cnty;
}
for(auto xd:zs)
{
newz[xd]=++cntz;
}
for(ll i=1;i<=q;++i)
{
cin>>x[i]>>y[i]>>z[i];
xs.insert({x[i],-i});
auto it=ys.lower_bound(y[i]);
if(it==ys.end())y[i]=cnty+1;
else y[i]=newy[(*it)];
it=zs.lower_bound(z[i]);
if(it==zs.end())z[i]=cntz+1;
else z[i]=newz[(*it)];
}
for(auto xd:xs)
{
newx[xd]=++cntx;
}
for(ll i=1;i<=n;++i)
{
s[i]=newx[{s[i],i}];
t[i]=newy[t[i]];
sum[i]=newz[sum[i]];
}
for(ll i=1;i<=q;i++)
{
x[i]=newx[{x[i],-i}];
}
//cout<<"students:\n";
for(ll i=1;i<=n;++i)
{
//cout<<s[i]<<" "<<t[i]<<" "<<sum[i]<<endl;
blocks1[s[i]/SQRT].push_back({s[i],t[i],sum[i]});
}
//cout<<"criterias:\n";
for(ll i=1;i<=q;++i)
{
//cout<<x[i]<<" "<<y[i]<<" "<<z[i]<<endl;
blocks2[x[i]/SQRT].push_back({x[i],y[i],z[i],i});
}
vector<student>computed,eh,oh;
for(ll j=SQRT-1;j>=0;--j)
{
if(blocks1[j].size()==0&&blocks2[j].size()==0)continue;
memset(BIT,0,sizeof(BIT));
/*cout<<"block1 "<<j<<":\n";
for(ll i=0;i<blocks1[j].size();++i)
{
cout<<blocks1[j][i].a<<" "<<blocks1[j][i].b<<" "<<blocks1[j][i].c<<"\n";
}
cout<<endl;
cout<<"block2 "<<j<<":\n";
for(ll i=0;i<blocks2[j].size();++i)
{
cout<<blocks2[j][i].a<<" "<<blocks2[j][i].b<<" "<<blocks2[j][i].c<<" "<<blocks2[j][i].pos<<"\n";
}
cout<<endl;*/
for(ll i1=0;i1<blocks2[j].size();++i1)
{
for(ll i2=0;i2<blocks1[j].size();++i2)
{
if(blocks2[j][i1].a<=blocks1[j][i2].a&&blocks2[j][i1].b<=blocks1[j][i2].b&&blocks2[j][i1].c<=blocks1[j][i2].c)
{
ans[blocks2[j][i1].pos]++;
}
}
}
sort(blocks2[j].rbegin(),blocks2[j].rend());
ll p=computed.size()-1;
for(ll i=0;i<blocks2[j].size();++i)
{
while(p>0&&computed[p].b>=blocks2[j][i].b)
{
update(computed[p].c,+1);
p--;
}
ans[blocks2[j][i].pos]+=(computed.size()-p-1)-query(blocks2[j][i].c-1);
}
eh.clear();
for(ll i=0;i<blocks1[j].size();++i)
{
eh.push_back(blocks1[j][i]);
}
sort(eh.begin(),eh.end());
oh.clear();
ll i1=0,i2=0;
while(i1<eh.size()||i2<computed.size())
{
if(i1==eh.size())
{
oh.push_back(computed[i2]);
++i2;
}
else if(i2==computed.size())
{
oh.push_back(eh[i1]);
++i1;
}
else if(eh[i1]<computed[i2])
{
oh.push_back(eh[i1]);
++i1;
}
else
{
oh.push_back(computed[i2]);
++i2;
}
}
computed=oh;
/*cout<<"computed:\n";
for(ll j=0;j<computed.size();j++)
{
cout<<computed[j].a<<" "<<computed[j].b<<" "<<computed[j].c<<endl;
}*/
}
for(ll i=1;i<=q;++i)
{
cout<<ans[i]<<"\n";
}
return 0;
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:142:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(ll i1=0;i1<blocks2[j].size();++i1)
| ~~^~~~~~~~~~~~~~~~~~
examination.cpp:144:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(ll i2=0;i2<blocks1[j].size();++i2)
| ~~^~~~~~~~~~~~~~~~~~
examination.cpp:154:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for(ll i=0;i<blocks2[j].size();++i)
| ~^~~~~~~~~~~~~~~~~~
examination.cpp:164:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for(ll i=0;i<blocks1[j].size();++i)
| ~^~~~~~~~~~~~~~~~~~
examination.cpp:171:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | while(i1<eh.size()||i2<computed.size())
| ~~^~~~~~~~~~
examination.cpp:171:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | while(i1<eh.size()||i2<computed.size())
| ~~^~~~~~~~~~~~~~~~
examination.cpp:173:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | if(i1==eh.size())
| ~~^~~~~~~~~~~
examination.cpp:178:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
178 | else if(i2==computed.size())
| ~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 7 |
Incorrect |
25 ms |
4972 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1998 ms |
66128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1998 ms |
66128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 7 |
Incorrect |
25 ms |
4972 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
