#include <iostream>
#include <vector>
#include <tuple>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <array>
#include <random>
#include <climits>
#include <cassert>
#include <algorithm>
using namespace std;
template<typename A, typename B> ostream& operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator << (ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) { os << sep << x, sep = ", "; } return os << '}'; }
void D_out() { cerr << endl; }
template<typename Head, typename... Tail> void D_out(Head H, Tail... T) { cerr << ' ' << H; D_out(T...); }
#ifdef DEBUG
#define D(...) cerr << '(' << #__VA_ARGS__ << "):", D_out(__VA_ARGS__)
#else
#define D(...)
#endif
//#define int long long
#define ll long long
#define ld long double
#define f first
#define s second
#define sz(x) ((int) x.size())
#define all(x) (x).begin(), (x).end()
#define lowbit(x) (x & (-x))
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
struct Event {
int a, b, c, idx;
Event (): a(0), b(0), c(0), idx(0) {}
Event (int ta, int tb, int tc, int tidx): a(ta), b(tb), c(tc), idx(tidx) {}
};
struct BIT {
int bit[200005];
vector<int> nodes;
void update(int x, int v) {
nodes.push_back(x);
for (; x; x -= lowbit(x)) {
bit[x] += v;
}
}
int query(int x) {
int ret = 0;
for (; x < 200005; x += lowbit(x)) {
ret += bit[x];
}
return ret;
}
void reset() {
for (int x : nodes) {
bit[x] = 0;
}
nodes.clear();
}
};
int n, q, sz, ans[100005];
Event events[200005];
vector<int> coordx, coordy, coordz;
BIT bt;
void cdq(int l, int r) {
if (l == r) return;
int m = (l + r) / 2;
cdq(l, m);
cdq(m + 1, r);
for (int lidx = l, ridx = m; lidx <= m; lidx++) {
while (ridx < r && events[lidx].b <= events[ridx + 1].b) {
ridx++;
if (!events[ridx].idx) {
bt.update(events[ridx].c, 1);
}
}
if (events[lidx].idx) {
ans[events[lidx].idx] += bt.query(events[lidx].c);
}
}
bt.reset();
inplace_merge(events + l, events + m + 1, events + r + 1, [&] (Event lft, Event rht) {
return lft.b > rht.b;
});
}
void solve() {
cin >> n >> q;
for (int i = 0, s, t; i < n; i++) {
cin >> s >> t;
events[sz++] = Event(s, t, s + t, 0);
coordx.push_back(s);
coordy.push_back(t);
coordz.push_back(s + t);
}
for (int i = 1, x, y, z; i <= q; i++) {
cin >> x >> y >> z;
events[sz++] = Event(x, y, z, i);
coordx.push_back(x);
coordy.push_back(y);
coordz.push_back(z);
}
sort(all(coordx));
sort(all(coordy));
sort(all(coordz));
coordx.erase(unique(all(coordx)), coordx.end());
coordy.erase(unique(all(coordy)), coordy.end());
coordz.erase(unique(all(coordz)), coordz.end());
for (int i = 0; i < sz; i++) {
events[i].a = lower_bound(all(coordx), events[i].a) - coordx.begin() + 1;
events[i].b = lower_bound(all(coordy), events[i].b) - coordy.begin() + 1;
events[i].c = lower_bound(all(coordz), events[i].c) - coordz.begin() + 1;
}
sort(events, events + sz, [&] (Event lft, Event rht) {
if (lft.a != rht.a) return lft.a < rht.a;
else if (lft.b != rht.b) return lft.b < rht.b;
else if (lft.c != rht.c) return lft.c < rht.c;
return lft.idx > rht.idx;
});
cdq(0, sz - 1);
for (int i = 1; i <= q; i++) {
cout << ans[i] << "\n";
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1; //cin >> t;
for (int tc = 1; tc <= t; tc++) {
//cout << "Case #" << tc << ": ";
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
250 ms |
14368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
250 ms |
14368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
