#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define debug(...) {}
#endif
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector S(n, 0), T(n, 0), K(n, 0);
vector<int> values;
REP (i, n) {
cin >> S[i] >> T[i];
values.emplace_back(S[i]);
values.emplace_back(T[i]);
K[i] = S[i] + T[i];
values.emplace_back(K[i]);
}
vector<tuple<int, int, int>> queries(q);
for (auto &[a, b, c] : queries) {
cin >> a >> b >> c;
values.emplace_back(a);
values.emplace_back(b);
values.emplace_back(c);
}
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
auto scale = [&](int x) {
return (int)(lower_bound(values.begin(), values.end(), x) - values.begin());
};
for (int &i : S)
i = scale(i);
for (int &i : T)
i = scale(i);
for (int &i : K)
i = scale(i);
for (auto &[a, b, c] : queries) {
a = scale(a);
b = scale(b);
c = scale(c);
debug(a, b, c);
}
debug(S);
debug(T);
debug(K);
vector<int> ans(q);
auto merge = [&](vector<int> point_id, vector<int> query_id) {
sort(point_id.begin(), point_id.end(), [&](int x, int y) {
return S[x] < S[y];});
sort(query_id.begin(), query_id.end(), [&](int x, int y) {
return get<0>(queries[x]) < get<0>(queries[y]);});
debug(point_id);
debug(query_id);
for (int i : point_id) {
for (int j : query_id) {
auto [a, b, c] = queries[j];
debug(j, i, S[i], a, T[i], b, K[i], c, (S[i] >= a && T[i] >= b && K[i] >= c));
ans[j] += (S[i] >= a && T[i] >= b && K[i] >= c);
}
}
};
function<void(int, int, vector<int>, vector<int>)> rek =
[&](int lf, int rg, vector<int> point_id, vector<int> query_id) {
if (lf == rg) {
merge(point_id, query_id);
return;
}
int mid = (lf + rg) / 2;
vector<int> left_point_id, right_point_id, left_query_id, right_query_id;
for (int i : point_id) {
if (S[i] + T[i] <= mid)
left_point_id.emplace_back(i);
else
right_point_id.emplace_back(i);
}
for (int i : query_id) {
if (get<2>(queries[i]) <= mid)
left_query_id.emplace_back(i);
else
right_query_id.emplace_back(i);
}
merge(right_point_id, left_query_id);
rek(lf, mid, left_point_id, left_query_id);
rek(mid + 1, rg, right_point_id, right_query_id);
};
vector<int> point_id(n), query_id(q);
iota(point_id.begin(), point_id.end(), 0);
iota(query_id.begin(), query_id.end(), 0);
rek(0, ssize(values) - 1, point_id, query_id);
//merge(point_id, query_id);
REP (i, q)
cout << ans[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
320 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
316 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
33 ms |
872 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3078 ms |
11612 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3078 ms |
11612 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
320 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
316 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
33 ms |
872 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
