#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;
// Query/Update: O(Nlog^2N)
// Memory: O(NlogN)
struct BIT_2D_Offline {
int n;
vector<vector<int> > tree, vals;
BIT_2D_Offline(int n, vector<pii> &U) : n(n), vals(n+1), tree(n+1) {
sort(U.begin(), U.end(), [&](pii &a, pii &b) { return a.second < b.second; });
for(int i=1; i<=n; i++) vals[i].push_back( 0 );
for(auto &[x, y]: U)
for(; x<=n; x+=x&-x)
if(vals[x].back() != y) vals[x].push_back(y);
for(int i=1; i<=n; i++) tree[i].resize( vals[i].size() );
}
int getId(int i, int v) {
return upper_bound( vals[i].begin(), vals[i].end(), v ) - vals[i].begin() - 1;
}
void update(int x, int y, int v) {
for(; x<=n; x+=x&-x)
for(int p=getId(x, y); p<tree[x].size(); p+=p&-p) tree[x][p] += v;
}
int Q(int x, int y) {
if(x <= 0 || y <= 0) return 0;
int ans = 0;
for(; x; x-=x&-x)
for(int p=getId(x, y); p; p-=p&-p) ans += tree[x][p];
return ans;
}
int query(int x1, int y1, int x2, int y2) {
if(x1 > x2 || y1 > y2) return 0;
return Q(x2, y2) - Q(x1-1, y2) - Q(x2, y1-1) + Q(x1-1, y1-1);
}
};
int32_t main() {
ios_base::sync_with_stdio(false);
cout.tie(0); cin.tie(0);
int n, q;
cin >> n >> q;
vector<pii> v(n);
set<int> s; s.insert(0);
for(pii &x : v) {
cin >> x.first >> x.second;
s.insert(x.first);
s.insert(x.second);
}
vector<array<int, 4> > qus(q);
for(int i=0; i<q; i++) {
cin >> qus[i][0] >> qus[i][1] >> qus[i][2];
qus[i][3] = i;
s.insert(qus[i][0]);
s.insert(qus[i][1]);
s.insert(qus[i][2]);
}
vector<int> comp(all(s));
vector<pii> U;
for(auto &x : v) U.push_back(x);
BIT_2D_Offline bit(maxn, U);
sort(qus.begin(), qus.end(), [&](array<int, 4> &a, array<int, 4> &b) {
return a[2] > b[2];
});
sort(v.begin(), v.end(), [&](pii &a, pii &b) {
return a.first + a.second > b.first + b.second;
});
vector<int> ans(q);
int j=-1;
for(auto &qu : qus) {
while(j+1 < n && v[j+1].first + v[j+1].second >= qu[2]) {
j++;
bit.update(v[j].first, v[j].second, 1);
}
ans[qu[3]] = bit.query(qu[0], qu[1], maxn-1, maxn-1);
}
for(int &x : ans) cout << x << '\n';
return 0;
}
Compilation message
examination.cpp: In constructor 'BIT_2D_Offline::BIT_2D_Offline(int, std::vector<std::pair<int, int> >&)':
examination.cpp:25:29: warning: 'BIT_2D_Offline::vals' will be initialized after [-Wreorder]
25 | vector<vector<int> > tree, vals;
| ^~~~
examination.cpp:25:23: warning: 'std::vector<std::vector<int> > BIT_2D_Offline::tree' [-Wreorder]
25 | vector<vector<int> > tree, vals;
| ^~~~
examination.cpp:27:2: warning: when initialized here [-Wreorder]
27 | BIT_2D_Offline(int n, vector<pii> &U) : n(n), vals(n+1), tree(n+1) {
| ^~~~~~~~~~~~~~
examination.cpp: In member function 'void BIT_2D_Offline::update(int, int, int)':
examination.cpp:44:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int p=getId(x, y); p<tree[x].size(); p+=p&-p) tree[x][p] += v;
| ~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
11356 KB |
Output is correct |
| 2 |
Runtime error |
10 ms |
16476 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
132 ms |
35788 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
132 ms |
35788 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
11356 KB |
Output is correct |
| 2 |
Runtime error |
10 ms |
16476 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
