#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
struct Data
{
int s, t, sum, id;
Student()
{
s = 0;
t = 0;
sum = 0;
id = 0;
}
};
int n, q;
int ans[MAXN];
vector <int> S, T;
vector <int> Value[MAXN], BIT[MAXN];
vector <Data> Student, Query, Query2D;
void Unique(vector <int> &A)
{
sort(A.begin(), A.end());
A.erase(unique(A.begin(), A.end()), A.end());
}
void Change(vector <Data> &A)
{
for(auto &x : A)
{
x.s = S.end() - lower_bound(S.begin(), S.end(), x.s);
x.t = T.end() - lower_bound(T.begin(), T.end(), x.t);
}
}
int GetPos(vector <int> A, int b)
{
return lower_bound(A.begin(), A.end(), b) - A.begin();
}
void FakeUpdate(int x, int y)
{
for(x; x < MAXN; x += x & -x)
{
Value[x].push_back(y);
}
}
void FakeGet(int x, int y)
{
for(x; x > 0; x -= x & -x)
{
Value[x].push_back(y);
}
}
void Update(int x, int y)
{
for(x; x < MAXN; x += x & -x)
{
for(int id = GetPos(Value[x], y); id < (int)BIT[x].size(); id += id & -id)
{
BIT[x][id]++;
}
}
}
int Get(int x, int y)
{
int ans = 0;
for(x; x > 0; x -= x & -x)
{
for(int id = GetPos(Value[x], y); id > 0; id -= id & -id)
{
ans += BIT[x][id];
}
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
Student.resize(n);
for(int i = 0; i < n; i++)
{
cin >> Student[i].s >> Student[i].t;
S.push_back(Student[i].s);
T.push_back(Student[i].t);
Student[i].sum = Student[i].s + Student[i].t;
Student[i].id = -1;
}
Query.resize(q);
for(int i = 0; i < q; i++)
{
cin >> Query[i].s >> Query[i].t >> Query[i].sum;
S.push_back(Query[i].s);
T.push_back(Query[i].t);
Query[i].id = i;
}
sort(Student.begin(), Student.end(), [](Data A, Data B)
{
return A.sum > B.sum;
});
sort(Query.begin(), Query.end(), [](Data A, Data B)
{
return A.sum > B.sum;
});
Unique(S);
Unique(T);
Change(Student);
Change(Query);
int pt0 = 0, pt1 = 0;
while(pt0 < (int)Student.size() and pt1 < (int)Query.size())
{
if(Student[pt0].sum >= Query[pt1].sum)
{
Query2D.push_back(Student[pt0]);
pt0++;
}
else
{
Query2D.push_back(Query[pt1]);
pt1++;
}
}
while(pt1 < (int)Query.size())
{
Query2D.push_back(Query[pt1]);
pt1++;
}
for(auto x : Query2D)
{
if(x.id == -1)
{
FakeUpdate(x.s, x.t);
}
else
{
FakeGet(x.s, x.t);
}
}
for(int i = 1; i < MAXN; i++)
{
Value[i].push_back(0);
Unique(Value[i]);
BIT[i].resize(Value[i].size() + 1);
}
for(auto x : Query2D)
{
if(x.id == -1)
{
Update(x.s, x.t);
}
else
{
ans[x.id] = Get(x.s, x.t);
}
}
for(int i = 0; i < q; i++)
{
cout << ans[i] << '\n';
}
}
Compilation message
examination.cpp:9:5: error: ISO C++ forbids declaration of 'Student' with no type [-fpermissive]
9 | Student()
| ^~~~~~~
examination.cpp: In member function 'int Data::Student()':
examination.cpp:15:5: warning: no return statement in function returning non-void [-Wreturn-type]
15 | }
| ^
examination.cpp: In function 'void FakeUpdate(int, int)':
examination.cpp:46:9: warning: statement has no effect [-Wunused-value]
46 | for(x; x < MAXN; x += x & -x)
| ^
examination.cpp: In function 'void FakeGet(int, int)':
examination.cpp:54:9: warning: statement has no effect [-Wunused-value]
54 | for(x; x > 0; x -= x & -x)
| ^
examination.cpp: In function 'void Update(int, int)':
examination.cpp:62:9: warning: statement has no effect [-Wunused-value]
62 | for(x; x < MAXN; x += x & -x)
| ^
examination.cpp: In function 'int Get(int, int)':
examination.cpp:74:9: warning: statement has no effect [-Wunused-value]
74 | for(x; x > 0; x -= x & -x)
| ^
