이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int n, q, A[N + 5], B[N + 5], X[N + 5], Y[N + 5], Z[N + 5], arrIndex[N + 5], queryIndex[N + 5], ans[N + 5];
vector<int> node[2*N + 5], tree[2*N + 5];
void fakeUpdate(int x, int y) {
for (; x <= 2*N; x += x&-x) node[x].push_back(y);
}
void fakeQuery(int x, int y){
for (; x; x -= x&-x) node[x].push_back(y);
}
void compress() {
for (int i = 1; i <= 2*N; i++) {
sort(node[i].begin(), node[i].end());
node[i].erase(unique(node[i].begin(), node[i].end()), node[i].end());
tree[i].resize(node[i].size() + 1);
}
}
void update(int x, int y, int v) {
for (; x <= 2*N; x += x&-x) {
for (int yy = lower_bound(node[x].begin(), node[x].end(), y) - node[x].begin() + 1; yy <= node[x].size(); yy += yy&-yy) {
tree[x][yy] += v;
}
}
}
int query(int x, int y) {
int res = 0;
for (; x; x -= x&-x) {
for (int yy = lower_bound(node[x].begin(), node[x].end(), y) - node[x].begin() + 1; yy; yy -= yy&-yy) {
res += tree[x][yy];
}
}
return res;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> A[i] >> B[i];
for (int i = 1; i <= q; i++) cin >> X[i] >> Y[i] >> Z[i];
vector<int> mp1, mp2;
for (int i = 1; i <= n; i++) mp1.push_back(A[i]), mp2.push_back(B[i]);
for (int i = 1; i <= q; i++) mp1.push_back(X[i]), mp2.push_back(Y[i]);
sort(mp1.begin(), mp1.end());
sort(mp2.begin(), mp2.end());
auto getIndex = [&](int a, vector<int>&p) { return lower_bound(p.begin(), p.end(), a) - p.begin() + 1; };
iota(arrIndex + 1, arrIndex + n + 1, 1ll);
sort(arrIndex + 1, arrIndex + n + 1, [&](int a, int b) {
tuple<int, int, int> f = {A[a] + B[a], A[a], B[a]}, se = {A[b] + B[b], A[b], B[b]};
return f > se;
});
iota(queryIndex + 1, queryIndex + q + 1, 1ll);
sort(queryIndex + 1, queryIndex + q + 1, [&](int a, int b) {
tuple<int, int, int> f = {Z[a], X[a], Y[a]}, se = {Z[b], X[b], Y[b]};
return f > se;
});
for (int i = 1; i <= q; i++) {
int mpX = getIndex(X[i], mp1), mpY = getIndex(Y[i], mp2);
fakeQuery(2*N, 2*N);
fakeQuery(2*N, mpY - 1);
fakeQuery(mpX - 1, 2*N);
fakeQuery(mpX - 1, mpY - 1);
}
for (int i = 1; i <= n; i++) {
int mpA = getIndex(A[i], mp1), mpB = getIndex(B[i], mp2);
fakeUpdate(mpA, mpB);
}
compress();
for (int i = 1, index = 1; i <= q; i++) {
int pos = queryIndex[i];
while (index <= n && A[arrIndex[index]] + B[arrIndex[index]] >= Z[pos]) {
int mpA = getIndex(A[arrIndex[index]], mp1), mpB = getIndex(B[arrIndex[index]], mp2);
update(mpA, mpB, 1);
index++;
}
int mpX = getIndex(X[pos], mp1), mpY = getIndex(Y[pos], mp2);
ans[pos] = query(2*N, 2*N) - query(2*N, mpY - 1) - query(mpX - 1, 2*N) + query(mpX - 1, mpY - 1);
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
examination.cpp: In function 'void update(int, int, int)':
examination.cpp:27:90: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for (int yy = lower_bound(node[x].begin(), node[x].end(), y) - node[x].begin() + 1; yy <= node[x].size(); yy += yy&-yy) {
| ~~~^~~~~~~~~~~~~~~~~
# | 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... |