이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
struct lisan : vector<int> {
void done() { sort(AI()), erase(unique(AI()), end()); }
int operator()(int i) { return lower_bound(AI(), i) - begin(); }
};
const int MAX_N = 100010, MAX_M = MAX_N << 1, MAX_C = MAX_M;
int n, q;
int res[MAX_N];
const int QT = 0, MT = 1, LT = 1, RT = 0;
// big one comes first
struct info {
int a, b, c, tp, id, sd;
tuple<int,int,int,int,int> gtp() {
return make_tuple(a, b, c, sd, tp);
}
info (int a, int b, int c, int tp, int id = -1, int sd = -1) :
a(a), b(b), c(c), tp(tp), id(id), sd(sd) {}
info () :
a(0), b(0), c(0), tp(0), id(0), sd(0) {}
} arr[MAX_M] ;
bool operator < (info a, info b) {
return a.gtp() > b.gtp();
}
struct rbit {
int n;
vector<int> val;
rbit(int _n) : n(_n + 10) {
val.resize(n);
}
void add(int i, int d) {
for (;i;i ^= i&-i)
val[i] += d;
}
int qry(int i) {
int res = 0;
for (;i < n;i += i&-i)
res += val[i];
return res;
}
};
rbit tree(0);
void solve(int l, int r) {
// for (int i = l;i < r;++i)
// for (int j = l;j < i;++j)
// if (arr[j].b >= arr[i].b &&
// arr[j].c >= arr[i].c) {
// if (arr[j].tp == MT && arr[i].tp == QT) {
// ++res[ arr[i].id ];
// }
// }
//
// return;
if (r-l <= 1) return;
int mid = l + r >> 1;
solve(l, mid), solve(mid, r);
for (int i = l;i < mid;++i) {
auto &[a, b, c, tp, id, sd] = arr[i];
sd = LT;
}
for (int i = mid;i < r;++i) {
auto &[a, b, c, tp, id, sd] = arr[i];
sd = RT;
}
DE(l, mid, r);
auto cmp = [&](info x, info y) {
auto [a, b, c, tp, id, sd] = x;
auto [aa, bb, cc, tpp, idd, sdd] = y;
return make_tuple(b, c, tp, sd) >
make_tuple(bb, cc, tpp, sdd);
};
inplace_merge(arr+l, arr+mid, arr+r, cmp);
for (int i = l;i < r;++i) {
auto &[a, b, c, tp, id, sd] = arr[i];
DE(a, b, c, tp, id, sd);
if (sd == LT && tp == MT)
tree.add(c, 1);
if (sd == RT && tp == QT) {
DE(a, b, c, tp, id, sd);
//DE(tree.qry(c));
res[id] += tree.qry(c);
}
}
for (int i = l;i < r;++i) {
auto &[a, b, c, tp, id, sd] = arr[i];
if (sd == LT && tp == MT)
tree.add(c, -1);
}
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
for (int i = 0;i < n;++i) {
int a, b;
cin >> a >> b;
arr[i] = {a, b, a + b, MT};
}
for (int i = 0;i < q;++i) {
int a, b, c;
cin >> a >> b >> c;
arr[i + n] = {a, b, c, QT, i};
}
sort(arr, arr + n + q);
{
lisan L; L.reserve(n + q);
for (int i = 0;i < n + q;++i) {
auto [a, b, c, tp, id, sd] = arr[i];
L.pb(c);
}
L.done();
for (int i = 0;i < n + q;++i) {
auto &[a, b, c, tp, id, sd] = arr[i];
c = L(c) + 1;
}
}
tree = rbit(n + q + 10);
solve(0, n + q);
for (int i = 0;i < q;++i)
cout << res[i] << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
examination.cpp: In function 'void solve(int, int)':
examination.cpp:78:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | int mid = l + r >> 1;
| ~~^~~
examination.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
examination.cpp:90:2: note: in expansion of macro 'DE'
90 | DE(l, mid, r);
| ^~
examination.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
examination.cpp:102:3: note: in expansion of macro 'DE'
102 | DE(a, b, c, tp, id, sd);
| ^~
examination.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
examination.cpp:108:4: note: in expansion of macro 'DE'
108 | DE(a, b, c, tp, id, sd);
| ^~
# | 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... |