//八(＾□＾*)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
const int SQRT=350;
int n,q;
int ans[MAXN];
set<int>xs,ys,zs;
int s[MAXN],t[MAXN],sum[MAXN];
int x[MAXN],y[MAXN],z[MAXN];
map<int,int>newx,newy,newz;
struct student
{
int a,b,c;
student(){}
student(int _a,int _b,int _c)
{
a=_a;b=_b;c=_c;
}
bool operator<(student const& other)const
{
return b<other.b;
}
};
struct query
{
int a,b,c,pos;
query(){}
query(int _a,int _b,int _c,int _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];
int BIT[MAXN];
void update(int idx,int val)
{
++idx;
for(;idx<MAXN;idx+=idx&(-idx))
{
BIT[idx]+=val;
}
}
int query(int idx)
{
++idx;
int 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(int i=1;i<=n;++i)
{
cin>>s[i]>>t[i];
sum[i]=s[i]+t[i];
xs.insert(s[i]);ys.insert(t[i]);zs.insert(sum[i]);
}
int 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(int i=1;i<=n;++i)
{
s[i]=newx[s[i]];
t[i]=newy[t[i]];
sum[i]=newz[sum[i]];
}
for(int i=1;i<=q;++i)
{
cin>>x[i]>>y[i]>>z[i];
auto it=xs.lower_bound(x[i]);
if(it==xs.end())x[i]=cntx+1;
else x[i]=newx[(*it)];
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(int i=1;i<=n;++i)
{
blocks1[s[i]/SQRT].push_back({s[i],t[i],sum[i]});
}
for(int i=1;i<=q;++i)
{
blocks2[x[i]/SQRT].push_back({x[i],y[i],z[i],i});
}
vector<student>computed,eh,oh;
for(int j=SQRT-1;j>=0;--j)
{
if(blocks1[j].size()==0&&blocks2[j].size()==0)continue;
memset(BIT,0,sizeof(BIT));
for(int i1=0;i1<blocks2[j].size();++i1)
{
for(int 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());
int p=computed.size()-1;
for(int 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(int i=0;i<blocks1[j].size();++i)
{
eh.push_back(blocks1[j][i]);
}
sort(eh.begin(),eh.end());
oh.clear();
int 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;
}
for(int i=1;i<=q;++i)
{
cout<<ans[i]<<"\n";
}
return 0;
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int i1=0;i1<blocks2[j].size();++i1)
| ~~^~~~~~~~~~~~~~~~~~
examination.cpp:118:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int i2=0;i2<blocks1[j].size();++i2)
| ~~^~~~~~~~~~~~~~~~~~
examination.cpp:128:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int i=0;i<blocks2[j].size();++i)
| ~^~~~~~~~~~~~~~~~~~
examination.cpp:138:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i=0;i<blocks1[j].size();++i)
| ~^~~~~~~~~~~~~~~~~~
examination.cpp:145:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | while(i1<eh.size()||i2<computed.size())
| ~~^~~~~~~~~~
examination.cpp:145:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | while(i1<eh.size()||i2<computed.size())
| ~~^~~~~~~~~~~~~~~~
examination.cpp:147:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | if(i1==eh.size())
| ~~^~~~~~~~~~~
examination.cpp:152:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | else if(i2==computed.size())
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| 3 |
Correct |
1 ms |
748 KB |
Output is correct |
| 4 |
Correct |
1 ms |
748 KB |
Output is correct |
| 5 |
Correct |
1 ms |
748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
748 KB |
Output is correct |
| 7 |
Incorrect |
17 ms |
2028 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1276 ms |
31420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1276 ms |
31420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| 3 |
Correct |
1 ms |
748 KB |
Output is correct |
| 4 |
Correct |
1 ms |
748 KB |
Output is correct |
| 5 |
Correct |
1 ms |
748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
748 KB |
Output is correct |
| 7 |
Incorrect |
17 ms |
2028 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
