이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
//#define int ll
struct query {
int a, b, sum, id;
query() {};
query(int a, int b, int sum, int id) : a(a), b(b), sum(sum), id(id) {};
};
const int N = 1e5 + 10;
unordered_map<int, int> t[N];
int ans[N], sz1, sz2;
inline void update(int a, int b) {
for (int i = a; i <= sz1; i += i & (-i)) {
for (int j = b; j <= sz2; j += j & (-j)) {
t[i][j]++;
}
}
}
inline int get(int a, int b) {
int res = 0;
for (int i = a; i > 0; i -= i & (-i)) {
for (int j = b; j > 0; j -= j & (-j)) {
res += t[i][j];
}
}
return res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(n), b(n), sa, sb, ss;
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
sa.pb(a[i]);
sb.pb(b[i]);
ss.pb(a[i] + b[i]);
}
vector<query> que(m);
for (int i = 0; i < m; i++) {
cin >> que[i].a >> que[i].b >> que[i].sum;
que[i].id = i;
sa.pb(que[i].a);
sb.pb(que[i].b);
ss.pb(que[i].sum);
}
sort(all(sa));
sort(all(sb));
sort(all(ss));
sa.resize(unique(all(sa)) - sa.begin());
sb.resize(unique(all(sb)) - sb.begin());
ss.resize(unique(all(ss)) - ss.begin());
vector<vector<pair<int, int>>> add(SZ(ss));
for (int i = 0; i < n; i++) {
int cs = lower_bound(all(ss), a[i] + b[i]) - ss.begin();
a[i] = upper_bound(all(sa), a[i]) - sa.begin();
b[i] = upper_bound(all(sb), b[i]) - sb.begin();
//cerr << a[i] << ' ' << b[i] << ' ' << cs << '\n';
add[cs].pb({a[i], b[i]});
}
vector<vector<pair<pair<int, int>, int>>> check(SZ(ss));
for (int i = 0; i < m; i++) {
que[i].sum = lower_bound(all(ss), que[i].sum) - ss.begin();
que[i].a = upper_bound(all(sa), que[i].a) - sa.begin();
que[i].b = upper_bound(all(sb), que[i].b) - sb.begin();
//cout << que[i].a << ' ' << que[i].b << ' ' << que[i].sum << '\n';
check[que[i].sum].pb(make_pair(make_pair(que[i].a, que[i].b), que[i].id));
}
sz1 = SZ(sa), sz2 = SZ(sb);
for (int i = SZ(ss) - 1; i >= 0; i--) {
for (auto it : add[i]) {
update(SZ(sa) - it.F + 1, SZ(sb) - it.S + 1);
}
for (auto it : check[i]) {
ans[it.S] = get(SZ(sa) - it.F.F + 1, SZ(sb) - it.F.S + 1);
}
}
for (int i = 0; i < m; i++) {
cout << ans[i] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |