#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;
const int MAX_N = 1e5 + 10;
const int MAX_Q = 1e5 + 10;
const int B = 330;
int S[MAX_N], T[MAX_N], ST[MAX_N];
int X[MAX_Q], Y[MAX_Q], Z[MAX_Q];
int ans[MAX_Q];
vector <int> pA[2 * MAX_N], pB[2 * MAX_N];
class FenwickTree {
private :
int N;
vector <int> fenwick;
public :
FenwickTree() {}
FenwickTree(const int &n) : N(n), fenwick(N + 1, 0) {}
void update(const int &idx, const int &val) {
for(int i = idx; i <= N; i += (i & -i)) {
fenwick[i] += val;
}
}
int get(const int &idx) {
int res = 0;
for(int i = idx; i >= 1; i -= (i & -i)) {
res += fenwick[i];
}
return res;
}
int query(const int &idx) {
return get(N) - get(idx);
}
};
class Query {
public :
int a, b, c, i;
Query() {}
Query(const int &a_, const int &b_, const int &c_, const int &i_) : a(a_), b(b_), c(c_), i(i_) {}
bool operator<(const Query &o) const {
return make_pair((a + B - 1) / B, b) < make_pair((o.a + B - 1) / B, o.b);
}
};
void compress(vector <int> &vec) {
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, Q;
cin >> N >> Q;
vector <int> sa({-1}), sb({-1}), sc({-1});
for(int i = 1; i <= N; i++) {
cin >> S[i] >> T[i];
ST[i] = S[i] + T[i];
sa.push_back(S[i]);
sb.push_back(T[i]);
sc.push_back(ST[i]);
}
for(int i = 1; i <= Q; i++) {
cin >> X[i] >> Y[i] >> Z[i];
sa.push_back(X[i]);
sb.push_back(Y[i]);
sc.push_back(Z[i]);
}
// Compress
compress(sa);
compress(sb);
compress(sc);
for(int i = 1; i <= N; i++) {
S[i] = lower_bound(sa.begin(), sa.end(), S[i]) - sa.begin();
T[i] = lower_bound(sb.begin(), sb.end(), T[i]) - sb.begin();
ST[i] = lower_bound(sc.begin(), sc.end(), ST[i]) - sc.begin();
pA[S[i]].push_back(i);
pB[T[i]].push_back(i);
}
for(int i = 1; i < sa.size(); i++) {
sort(pA[i].begin(), pA[i].end());
}
for(int i = 1; i < sb.size(); i++) {
sort(pB[i].begin(), pB[i].end());
}
for(int i = 1; i <= Q; i++) {
X[i] = lower_bound(sa.begin(), sa.end(), X[i]) - sa.begin();
Y[i] = lower_bound(sb.begin(), sb.end(), Y[i]) - sb.begin();
Z[i] = lower_bound(sc.begin(), sc.end(), Z[i]) - sc.begin();
}
// MO's algorithm
vector <Query> query;
for(int i = 1; i <= Q; i++) {
query.push_back(Query(X[i], Y[i], Z[i], i));
}
sort(query.begin(), query.end());
FenwickTree fw(sc.size());
int cur_l, cur_r;
for(int i = 0; i < Q; i++) {
auto [l, r, c, id] = query[i];
if(i == 0) {
cur_l = l, cur_r = r;
for(int i = 1; i <= N; i++) {
if(S[i] >= cur_l and T[i] >= cur_r) {
fw.update(ST[i], 1);
}
}
}
else {
while(cur_l > l) {
cur_l--;
for(auto idx : pA[cur_l]) {
if(T[idx] >= cur_r) {
fw.update(ST[idx], 1);
}
else {
break;
}
}
}
while(cur_r < r) {
for(auto idx : pB[cur_r]) {
if(S[idx] >= cur_l) {
fw.update(ST[idx], -1);
}
else {
break;
}
}
cur_r++;
}
while(cur_l < l) {
for(auto idx : pA[cur_l]) {
if(T[idx] >= cur_r) {
fw.update(ST[idx], -1);
}
else {
break;
}
}
cur_l++;
}
while(cur_r > r) {
cur_r--;
for(auto idx : pB[cur_r]) {
if(S[idx] >= cur_l) {
fw.update(ST[idx], 1);
}
else {
break;
}
}
}
}
ans[id] = fw.query(c);
}
for(int i = 1; i <= Q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 1; i < sa.size(); i++) {
| ~~^~~~~~~~~~~
examination.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int i = 1; i < sb.size(); i++) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9628 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 7 |
Correct |
17 ms |
10196 KB |
Output is correct |
| 8 |
Correct |
18 ms |
10092 KB |
Output is correct |
| 9 |
Correct |
19 ms |
10212 KB |
Output is correct |
| 10 |
Incorrect |
13 ms |
10160 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2505 ms |
21144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2505 ms |
21144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9628 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 7 |
Correct |
17 ms |
10196 KB |
Output is correct |
| 8 |
Correct |
18 ms |
10092 KB |
Output is correct |
| 9 |
Correct |
19 ms |
10212 KB |
Output is correct |
| 10 |
Incorrect |
13 ms |
10160 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
