#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
#define pii pair<int,int>
unordered_map<int,int> mp_m,mp_i,mp_a,av;
vector<int> BIT,cnt;
int sz=700,n,q;
int next(int x){return x + (x&(-x));}
int par(int x){return x - (x&(-x));}
bool cmp(pair<int,pair<pii,pii>>& a,pair<int,pair<pii,pii>>& b){
if(a.first!=b.first)return a.first<b.first;
if(a.first&1)return a.second.first.second<b.second.first.first;
return a.second.first.second>b.second.first.first;
}
int bin_find(int x,vector<int>& v){
int l=0,r=v.size()-1,ans=v.size();
while(l<=r){
int mid=(r+l)/2;
if(v[mid]<x)l=mid+1;
else {
ans=mid;
r=mid-1;
}
}
return ans;
}
void pupd(int x,int k){
//cout<<x<<' '<<k<<'\n';
for(int i=x;i<BIT.size();i=next(i))BIT[i]+=k;
}
int sum(int x){
int ans=0;
for(int i=x;i>0;i=par(i)){
ans+=BIT[i];
}
return ans;
}
int val(int l,int r){
return sum(r)-sum(l);
}
void add(int i,vector<vector<int>>& g,vector<int>& exam){
for(int x:g[i]){
cnt[x]++;
if(cnt[x]==2){
pupd(mp_a[exam[x]]+1,+1);
}
}
}
void del(int i,vector<vector<int>>& g,vector<int>& exam){
for(int x:g[i]){
if(cnt[x]==2){
pupd(mp_a[exam[x]]+1,-1);
}
cnt[x]--;
}
}
vector<vector<int>> math,info;
void MO(vector<int>& m,vector<int>& in,vector<int>& av,vector<int>& exam,vector<int>& id){
int x,y,z;
vector<pair<int,pair<pii,pii>>> qu(q);
vector<int> answer(q);
for(int i=0;i<q;i++){
cin>>x>>y>>z;
x=bin_find(x,m);
y=bin_find(y,in);
z=bin_find(z,av);
//cout<<x<<' '<<y<<' '<<z<<' '<<id[x]<<'\n';
qu[i]={id[y],{{x,y},{z,i}}};
}
sort(qu.begin(),qu.end(),cmp);
int l_math=m.size(),l_info=in.size();
for(int i=0;i<q;i++){
int min_math=qu[i].second.first.first,min_info=qu[i].second.first.second,min_av=qu[i].second.second.first;
//cout<<min_math<<' '<<min_info<<'\n';
if(min_av==av.size()){
answer[qu[i].second.second.second]=0;
continue;
}
//cout<<l_math<<' '<<l_info<<'\n';
while(l_math>min_math){
l_math--;
add(l_math,math,exam);
}
while(l_math<min_math){
del(l_math,math,exam);
l_math++;
}
//cout<<l_math<<' '<<l_info<<'\n';
while(l_info>min_info){
l_info--;
//cout<<l_info<<' ';
add(l_info,info,exam);
}
//cout<<l_info<<' ';
while(l_info<min_info){
del(l_info,info,exam);
l_info++;
}
//cout<<l_math<<' '<<l_info<<' '<<qu[i].second.second<<' '<<ans<<' '<<sum(min_av)<<'\n';
answer[qu[i].second.second.second]=val(min_av,BIT.size()-1);
}
for(int i=0;i<q;i++)cout<<answer[i]<<'\n';
}
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int x,y;
cin>>n>>q;
set<int> m,in,av;
cnt=vector<int>(n);
vector<int> exam_math(n),exam_info(n),exam_av(n),a,b,c;
for(int i=0;i<n;i++){
cin>>x>>y;
m.insert(x);
in.insert(y);
av.insert((x+y));
exam_math[i]=x;
exam_info[i]=y;
exam_av[i]=(x+y);
}
mp_m.reserve(131072);
mp_i.reserve(131072);
mp_a.reserve(131072);
int cntm=0,cnti=0,cnta=0;
for(int x:m){
mp_m[x]=cntm;
cntm++;
a.emplace_back(x);
}
for(int x:in){
mp_i[x]=cnti;
cnti++;
b.emplace_back(x);
}
for(int x:av){
mp_a[x]=cnta;
cnta++;
c.emplace_back(x);
}
BIT=vector<int> (cnta+1);
math=vector<vector<int>> (cntm,vector<int>());
info=vector<vector<int>> (cnti,vector<int>());
for(int i=0;i<n;i++){
math[mp_m[exam_math[i]]].push_back(i);
info[mp_i[exam_info[i]]].push_back(i);
}
vector<int> id(cnti+1);
int cur=0,cont=2e6;
for(int i=0;i<info.size();i++){
if(info[i].size()>=sz){
cont--;
id[i]=cont;
cont--;
cur=0;
}else if(info[i].size()+cur>=sz){
cur=0;
id[i]=cont;
cont--;
}else{
cur+=info[i].size();
id[i]=cont;
}
}
id[cnti]=cont-1;
MO(a,b,c,exam_av,id);
}
Compilation message
examination.cpp: In function 'void pupd(int, int)':
examination.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i=x;i<BIT.size();i=next(i))BIT[i]+=k;
| ~^~~~~~~~~~~
examination.cpp: In function 'void MO(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
examination.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | if(min_av==av.size()){
| ~~~~~~^~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:154:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for(int i=0;i<info.size();i++){
| ~^~~~~~~~~~~~
examination.cpp:155:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
155 | if(info[i].size()>=sz){
| ~~~~~~~~~~~~~~^~~~
examination.cpp:160:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
160 | }else if(info[i].size()+cur>=sz){
| ~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3540 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 7 |
Correct |
103 ms |
4752 KB |
Output is correct |
| 8 |
Runtime error |
13 ms |
9428 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3072 ms |
31208 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3072 ms |
31208 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3540 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 7 |
Correct |
103 ms |
4752 KB |
Output is correct |
| 8 |
Runtime error |
13 ms |
9428 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
