// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
struct BIT
{
ll n;
vector<vector<ll>> node, bit;
BIT(ll n) : n(n)
{
node.resize(n + 5);
bit.resize(n + 5);
}
void addNode_Update(ll x, ll y)
{
for (x; x <= n; x += x & (-x))
node[x].pb(y);
}
void addNode_Query(ll x, ll y)
{
for (x; x > 0; x -= x & (-x))
node[x].pb(y);
}
void init()
{
for (ll i=1; i<=n; i++)
{
sort(node[i].begin(), node[i].end());
node[i].resize(unique(node[i].begin(), node[i].end())-node[i].begin());
bit[i].assign(node.size()+5, 0);
}
}
void addNode_range(ll x1, ll y1, ll x2, ll y2)
{
addNode_Query(x2, y2);
addNode_Query(x1 - 1, y2);
addNode_Query(x2, y1 - 1);
addNode_Query(x1 - 1, y1 - 1);
}
void update(ll x, ll yy, ll val)
{
// cout << x << " " << yy << " " << val << " u\n";
for (x; x <= n; x += x & (-x))
for (ll y = lower_bound(node[x].begin(), node[x].end(), yy) - node[x].begin() + 1; y <= node[x].size(); y += y & (-y))
bit[x][y - 1] += val;
}
ll query(ll x, ll yy)
{
ll ans = 0;
// cout << x << " " << yy << " ";
for (x; x > 0; x -= x & (-x))
for (ll y = lower_bound(node[x].begin(), node[x].end(), yy) - node[x].begin() + 1; y > 0; y -= y & (-y))
ans += bit[x][y - 1];
// cout << ans << " q\n";
return ans;
}
ll range(ll x1, ll y1, ll x2, ll y2)
{
return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
}
};
pll a[200005];
vector<ll> nen;
ll ans[200005];
vector<pair<pll, pll>> Q;
bool cmp(pll a, pll b)
{
return a.fi + a.se > b.fi + b.se;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n, q;
cin >> n >> q;
for (ll i = 1; i <= n; i++)
{
cin >> a[i].fi >> a[i].se;
nen.pb(a[i].fi);
}
sort(a + 1, a + n + 1, cmp);
for (ll i = 1; i <= q; i++)
{
ll a, b, c;
cin >> a >> b >> c;
Q.pb({{c, i}, {a, b}});
nen.pb(a);
}
sort(nen.begin(), nen.end());
nen.resize(unique(nen.begin(), nen.end()) - nen.begin());
ll k = nen.size();
BIT A(k);
for (ll i = 1; i <= n; i++)
A.addNode_Update(lower_bound(nen.begin(), nen.end(), a[i].fi) - nen.begin() + 1, a[i].se);
sort(Q.begin(), Q.end(), greater<pair<pll, pll>>());
for (ll i = 0; i < q; i++)
A.addNode_range(lower_bound(nen.begin(), nen.end(), Q[i].se.fi) - nen.begin() + 1, Q[i].se.se, k, 1e9);
A.init();
ll ptr = 1;
for (ll i = 0; i < q; i++)
{
ll c = Q[i].fi.fi, idx = Q[i].fi.se, aa = Q[i].se.fi, bb = Q[i].se.se;
while (ptr <= n && a[ptr].fi + a[ptr].se >= c)
A.update(lower_bound(nen.begin(), nen.end(), a[ptr].fi) - nen.begin() + 1, a[ptr].se, 1), ptr++;
ans[idx] = A.range(lower_bound(nen.begin(), nen.end(), aa) - nen.begin() + 1, bb, k, 1e9);
//cout << aa << " " << bb << " " << c << endl;
}
for (ll i = 1; i <= q; i++)
cout << ans[i] << "\n";
}
Compilation message
examination.cpp: In member function 'void BIT::addNode_Update(long long int, long long int)':
examination.cpp:25:14: warning: statement has no effect [-Wunused-value]
25 | for (x; x <= n; x += x & (-x))
| ^
examination.cpp: In member function 'void BIT::addNode_Query(long long int, long long int)':
examination.cpp:31:14: warning: statement has no effect [-Wunused-value]
31 | for (x; x > 0; x -= x & (-x))
| ^
examination.cpp: In member function 'void BIT::update(long long int, long long int, long long int)':
examination.cpp:56:14: warning: statement has no effect [-Wunused-value]
56 | for (x; x <= n; x += x & (-x))
| ^
examination.cpp:57:98: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (ll y = lower_bound(node[x].begin(), node[x].end(), yy) - node[x].begin() + 1; y <= node[x].size(); y += y & (-y))
| ~~^~~~~~~~~~~~~~~~~
examination.cpp: In member function 'long long int BIT::query(long long int, long long int)':
examination.cpp:65:14: warning: statement has no effect [-Wunused-value]
65 | for (x; x > 0; x -= x & (-x))
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
107 ms |
284236 KB |
Output is correct |
| 8 |
Correct |
97 ms |
284184 KB |
Output is correct |
| 9 |
Correct |
97 ms |
284272 KB |
Output is correct |
| 10 |
Correct |
99 ms |
284140 KB |
Output is correct |
| 11 |
Runtime error |
6 ms |
1876 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
661 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
661 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
107 ms |
284236 KB |
Output is correct |
| 8 |
Correct |
97 ms |
284184 KB |
Output is correct |
| 9 |
Correct |
97 ms |
284272 KB |
Output is correct |
| 10 |
Correct |
99 ms |
284140 KB |
Output is correct |
| 11 |
Runtime error |
6 ms |
1876 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
