#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include "/Users/quocbaonguyentran/Documents/VOI25/template/debug.cpp"
#else
#define debug(...) ;
#endif
using namespace std;
#define endl "\n"
#define ll long long
struct Fenwick
{
vector<int> bit;
Fenwick() {};
Fenwick(int n) : bit(n + 1, 0) {}
void update(int id, int val)
{
for (; id < int(bit.size()); id += id & (-id))
{
bit[id] += val;
}
}
int sum(int id)
{
int sum = 0;
for (; id > 0; id -= id & (-id))
{
sum += bit[id];
}
return sum;
}
int query(int l, int r)
{
return sum(r) - sum(l - 1);
}
} tree;
vector<int> d;
int res[200005];
int n, s[100005], t[100005], q;
int qe[100005];
int ans[100005];
vector<tuple<int, int, int, int, char>> p;
vector<tuple<int, int, char>> query;
bool cmp(tuple<int, int, int, char> &a, tuple<int, int, int, char> &b)
{
int l1 = get<0>(a);
int l2 = get<0>(b);
char v1 = get<3>(a);
char v2 = get<3>(b);
return l1 > l2 || l1 == l2 && v1 < v2;
}
bool cmp2(tuple<int, int, int, int, char> &a, tuple<int, int, int, int, char> &b)
{
int l1 = get<0>(a);
int l2 = get<0>(b);
char v1 = get<4>(a);
char v2 = get<4>(b);
return l1 > l2 || l1 == l2 && v1 < v2;
}
void Cal(int l, int r)
{
if (l >= r)
return;
int mid = (l + r) / 2;
vector<tuple<int, int, int, char>> c;
for (int i = l; i <= mid; i++)
{
auto [l, r, w] = query[i];
if (w == '+')
{
c.push_back(make_tuple(l, r, i, w));
}
}
for (int i = mid + 1; i <= r; i++)
{
auto [l, r, w] = query[i];
if (w == '?')
{
c.push_back(make_tuple(l, r, i, w));
}
}
sort(c.begin(), c.end(), cmp);
vector<int> t;
for (auto [l, r, i, w] : c)
{
if (w == '+')
{
t.push_back(r);
tree.update(r, 1);
}
else
{
int val = tree.query(r, int(d.size()));
res[i] += val;
}
}
for (int i : t)
{
tree.update(i, -1);
}
Cal(l, mid);
Cal(mid + 1, r);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
cin >> s[i] >> t[i];
p.push_back({s[i] + t[i], s[i], t[i], i, '+'});
}
for (int i = 1; i <= q; i++)
{
int a, b, c;
cin >> a >> b >> c;
p.push_back({c, a, b, i, '?'});
}
sort(p.begin(), p.end(), cmp2);
query.push_back({0, 0, '0'});
d.push_back(1);
d.push_back(1e9);
for (auto [w, l, r, id, type] : p)
{
query.push_back({l, r, type});
if (type == '?')
qe[query.size() - 1] = id;
d.push_back(r);
}
sort(d.begin(), d.end());
d.erase(unique(d.begin(), d.end()), d.end());
for (auto &[l, r, w] : query)
{
r = lower_bound(d.begin(), d.end(), r) - d.begin() + 1;
}
tree = Fenwick(int(d.size()));
Cal(1, n + q);
for (int i = 1; i <= n + q; i++)
{
auto [l, r, w] = query[i];
if (w == '?')
{
// cout << res[i] << " " << qe[i] << endl;
ans[qe[i]] = res[i];
}
}
for (int i = 1; i <= q; i++)
{
cout << ans[i] << endl;
}
}
Compilation message
examination.cpp:3:10: fatal error: /Users/quocbaonguyentran/Documents/VOI25/template/debug.cpp: No such file or directory
3 | #include "/Users/quocbaonguyentran/Documents/VOI25/template/debug.cpp"
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.
