//八(＾□＾*)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
const int SQRT=500;
int n,q;
int ans[MAXN];
set<pair<int,int> >xs;
set<int>ys,zs;
int s[MAXN],t[MAXN],sum[MAXN];
int x[MAXN],y[MAXN],z[MAXN];
map<pair<int,int>,int>newx;
map<int,int>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];
xs.insert({s[i],i});
sum[i]=s[i]+t[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<=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(int i=1;i<=n;++i)
{
s[i]=newx[{s[i],i}];
t[i]=newy[t[i]];
sum[i]=newz[sum[i]];
}
for(int i=1;i<=q;i++)
{
x[i]=newx[{x[i],-i}];
}
//cout<<"students:\n";
for(int 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(int 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(int 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(int 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(int 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(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;
/*cout<<"computed:\n";
for(int j=0;j<computed.size();j++)
{
cout<<computed[j].a<<" "<<computed[j].b<<" "<<computed[j].c<<endl;
}*/
}
for(int i=1;i<=q;++i)
{
cout<<ans[i]<<"\n";
}
return 0;
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:141:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int i1=0;i1<blocks2[j].size();++i1)
| ~~^~~~~~~~~~~~~~~~~~
examination.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for(int i2=0;i2<blocks1[j].size();++i2)
| ~~^~~~~~~~~~~~~~~~~~
examination.cpp:153:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for(int i=0;i<blocks2[j].size();++i)
| ~^~~~~~~~~~~~~~~~~~
examination.cpp:163:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for(int i=0;i<blocks1[j].size();++i)
| ~^~~~~~~~~~~~~~~~~~
examination.cpp:170:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
170 | while(i1<eh.size()||i2<computed.size())
| ~~^~~~~~~~~~
examination.cpp:170:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
170 | while(i1<eh.size()||i2<computed.size())
| ~~^~~~~~~~~~~~~~~~
examination.cpp:172:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | if(i1==eh.size())
| ~~^~~~~~~~~~~
examination.cpp:177:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | else if(i2==computed.size())
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 7 |
Incorrect |
18 ms |
2796 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
892 ms |
76012 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
892 ms |
76012 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1132 KB |
Output is correct |
| 7 |
Incorrect |
18 ms |
2796 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
