#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define dbg(...) 17;
#endif
template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }
const int SZ = (1 << 17);
template<class T> struct Node {
T val = 0;
Node<T>* c[2];
Node() { c[0] = c[1] = NULL; }
void upd(int ind, T v, int L = 0, int R = SZ - 1) { // add v
if (L == ind && R == ind) { val += v; return; }
int M = (L + R) / 2;
if (ind <= M) {
if (!c[0]) c[0] = new Node();
c[0]->upd(ind, v, L, M);
} else {
if (!c[1]) c[1] = new Node();
c[1]->upd(ind, v, M + 1, R);
}
val = 0;
for (int i = 0; i < 2; i++)
if (c[i]) val += c[i]->val;
}
T query(int lo, int hi, int L = 0, int R = SZ - 1) { // query sum of segment
if (hi < L || R < lo) return 0;
if (lo <= L && R <= hi) return val;
int M = (L + R) / 2;
T res = 0;
if (c[0]) res += c[0]->query(lo, hi, L, M);
if (c[1]) res += c[1]->query(lo, hi, M + 1, R);
return res;
}
void update_2d(int ind, Node* c0, Node* c1, int L = 0, int R = SZ - 1) { // for 2D segtree
if (L != R) {
int M = (L + R) / 2;
if (ind <= M) {
if (!c[0]) c[0] = new Node();
c[0]->update_2d(ind, (c0 ? c0->c[0] : NULL), (c1 ? c1->c[0] : NULL), L, M);
} else {
if (!c[1]) c[1] = new Node();
c[1]->update_2d(ind, (c0 ? c0->c[1] : NULL), (c1 ? c1->c[1] : NULL), M + 1, R);
}
}
val = (c0 ? c0->val : 0) + (c1 ? c1->val : 0);
}
};
template<class T> struct BITSeg {
Node<T> seg[SZ];
BITSeg() {
for (int i = 0; i < SZ; i++)
seg[i] = Node<T>();
}
void upd(int x, int y, int v) { // add v
for (; x < SZ; x += x & -x)
seg[x].upd(y, v);
}
T query(int x, int y1, int y2) {
if (x < 0) return 0;
T res = 0;
for (; x; x -= x & -x)
res += seg[x].query(y1, y2);
return res;
}
T query(int x1, int x2, int y1, int y2) { // query sum of rectangle
return query(x2, y1, y2) - query(x1 - 1, y1, y2);
}
};
int main() {
typedef long long ll;
int n, q; cin >> n >> q;
vector<array<int, 2>> v(n);
set<int> xs, ys;
for (int i = 0; i < n; i++) {
cin >> v[i][0] >> v[i][1];
xs.insert(v[i][0]);
ys.insert(v[i][1]);
}
vector<int> ans(q);
vector<array<int, 4>> queries(q);
for (int i = 0; i < q; i++) {
queries[i][0] = i;
cin >> queries[i][1] >> queries[i][2] >> queries[i][3];
xs.insert(queries[i][1]);
ys.insert(queries[i][2]);
}
map<int, int> mx, my;
int cnt = 0;
for (int x : xs)
mx[x] = cnt, cnt++;
cnt = 0;
for (int y : ys)
my[y] = cnt, cnt++;
sort(queries.begin(), queries.end(), [](array<int, 4> a, array<int, 4> b) {
return a[3] < b[3];
});
sort(v.begin(), v.end(), [](array<int, 2> a, array<int, 2> b) {
return a[0] + a[1] < b[0] + b[1];
});
BITSeg<ll> seg;
int qv = n;
for (int i = q - 1; i >= 0; i--) {
int sum = queries[i][3];
while (qv > 0 && v[qv - 1][0] + v[qv - 1][1] >= sum) {
qv--;
seg.upd(mx[v[qv][0]], my[v[qv][1]], 1);
}
ans[queries[i][0]] = seg.query(mx[queries[i][1]], SZ - 1, my[queries[i][2]], SZ - 1);
}
for (int i = 0; i < q; i++)
cout << ans[i] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3081 ms |
3436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3085 ms |
258156 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3085 ms |
258156 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3081 ms |
3436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
