Submission #61737728
Source Code Expand
#include <array>
#include <numeric>
#include <algorithm>
#include <cassert>
#include <vector>
constexpr int bit_ceil_log(unsigned int n) {
int x = 0;
while ((1 << x) < (unsigned int)(n)) x++;
return x;
}
template<typename Idx, typename S, S (*op)(S, S), S (*e)(), typename F, S (*mapping)(F, S, int), F (*composition)(F, F), F (*id)()>
struct kd_tree_lazy {
public:
struct point {
Idx x, y;
S z;
point() {}
point(Idx x, Idx y, S z) : x(x), y(y), z(z) {}
};
private:
static constexpr Idx inf = std::numeric_limits<Idx>::max() / 2;
static constexpr Idx minf = -inf;
struct node {
Idx lx, rx, ly, ry;
int size;
S sum;
F lz;
node () : lx(inf), rx(minf), ly(inf), ry(minf), size(0), sum(e()), lz(id()){}
node (point p) : lx(p.x), rx(p.x), ly(p.y), ry(p.y), size(1), sum(p.z), lz(id()) {}
};
int log, sz;
std::vector<node> V{node()};
void update(int v) {
V[v].size = V[v * 2].size + V[v * 2 + 1].size;
V[v].lx = std::min(V[v * 2].lx, V[v * 2 + 1].lx);
V[v].rx = std::max(V[v * 2].rx, V[v * 2 + 1].rx);
V[v].ly = std::min(V[v * 2].ly, V[v * 2 + 1].ly);
V[v].ry = std::max(V[v * 2].ry, V[v * 2 + 1].ry);
update_val(v);
}
void update_val(int v) {
V[v].sum = op(V[v * 2].sum, V[v * 2 + 1].sum);
}
void all_apply(int v, F lz) {
V[v].sum = mapping(lz, V[v].sum, V[v].size);
V[v].lz = composition(lz, V[v].lz);
}
void push_down(int v) {
if (V[v].lz != id()) {
all_apply(v * 2, V[v].lz);
all_apply(v * 2 + 1, V[v].lz);
V[v].lz = id();
}
}
void build(std::vector<std::pair<point, int>> &v, int l, int r, bool dim) {
int len = r - l;
if (len == 1) {
V[l + sz] = node(v[l].first);
if (v[l].second != sz) info[v[l].second].second = l;
return;
}
int m = (l + r) / 2;
if (!dim) {
std::nth_element(v.begin() + l, v.begin() + m, v.begin() + r, [](const auto &a, const auto &b) { return a.first.x < b.first.x; });
} else {
std::nth_element(v.begin() + l, v.begin() + m, v.begin() + r, [](const auto &a, const auto &b) { return a.first.y < b.first.y; });
}
build(v, l, m, !dim);
build(v, m, r, !dim);
}
static std::array<int, 100000> que, st;
std::vector<std::pair<S, int>> info; // {値, 内部インデックス}
public:
kd_tree_lazy() {}
kd_tree_lazy(const std::vector<point> &v) {
log = bit_ceil_log(std::max(1, int(v.size())));
sz = 1 << log;
std::vector<std::pair<point, int>> P(sz, {point{inf, inf, e()}, sz});
for (int i = 0; i < int(v.size()); i++) P[i] = {v[i], i};
info.resize(sz, {e(), -1});
V.resize(2 * sz);
build(P, 0, sz, 0);
for (int i = sz - 1; i > 0; i--) update(i);
}
void on(int k) {
int t = info[k].second + sz;
for (int i = log; i > 0; i--) push_down(t >> i);
if (V[t].size == 1) return;
V[t].size = 1;
V[t].sum = info[k].first;
while (t > 1) {
t /= 2;
update(t);
}
}
void off(int k) {
int t = info[k].second + sz;
for (int i = log; i > 0; i--) push_down(t >> i);
info[k].first = V[t].sum;
V[t].size = 0;
V[t].sum = e();
while (t > 1) {
t /= 2;
update(t);
}
}
void set(int k, S x) {
int t = info[k].second + sz;
for (int i = log; i > 0; i--) push_down(t >> i);
assert(V[t].size == 1);
V[t].sum = x;
while (t > 1) {
t /= 2;
update(t);
}
}
S get(int k) {
int t = info[k].second + sz;
if (V[t].size == 0) return info[k].first;
for (int i = log; i > 0; i--) push_down(t >> i);
return V[t].sum;
}
// O(√N)
void apply_rectangle(Idx LX, Idx RX, Idx LY, Idx RY, F lz) {
RX--, RY--;
if (LX > RX || LY > RY) return;
int l = 0, r = 0;
int k = 0;
que[r++] = 1;
while (l < r) {
int v = que[l++];
if (V[v].size == 0 || V[v].rx < LX || RX < V[v].lx || V[v].ry < LY || RY < V[v].ly) continue;
if (LX <= V[v].lx && V[v].rx <= RX && LY <= V[v].ly && V[v].ry <= RY) {
all_apply(v, lz);
} else {
push_down(v);
que[r++] = v * 2;
que[r++] = v * 2 + 1;
st[k++] = v;
}
}
while (k--) update_val(st[k]);
}
// O(√N)
S prod_rectangle(Idx LX, Idx RX, Idx LY, Idx RY) {
RX--, RY--;
if (LX > RX || LY > RY) return e();
int l = 0, r = 0;
que[r++] = 1;
S res = e();
while (l < r) {
int v = que[l++];
if (V[v].size == 0 || V[v].rx < LX || RX < V[v].lx || V[v].ry < LY || RY < V[v].ly) continue;
if (LX <= V[v].lx && V[v].rx <= RX && LY <= V[v].ly && V[v].ry <= RY) {
res = op(res, V[v].sum);
} else {
push_down(v);
que[r++] = v * 2;
que[r++] = v * 2 + 1;
}
}
return res;
}
};
template<typename Idx, typename S, S (*op)(S, S), S (*e)(), typename F, S (*mapping)(F, S, int), F (*composition)(F, F), F (*id)()>
std::array<int, 100000> kd_tree_lazy<Idx, S, op, e, F, mapping, composition, id>::que;
template<typename Idx, typename S, S (*op)(S, S), S (*e)(), typename F, S (*mapping)(F, S, int), F (*composition)(F, F), F (*id)()>
std::array<int, 100000> kd_tree_lazy<Idx, S, op, e, F, mapping, composition, id>::st;
#include <iostream>
#include <tuple>
using S = long long;
static constexpr S op(S a, S b) {
return a + b;
}
static constexpr S e() {
return 0;
}
using F = long long;
static constexpr S mapping(F a, S b, int c) {
return b + a * c;
}
static constexpr F composition(F a, F b) {
return a + b;
}
static constexpr F id() {
return 0;
}
using kdt = kd_tree_lazy<int, S, op, e, F, mapping, composition, id>;
using point = typename kdt::point;
int main() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int N, Q;
std::cin >> N >> Q;
std::vector<point> P;
std::vector<std::tuple<int, int, int, int>> tmp;
for (int i = 0; i < N; i++) {
int x, y, d, c;
std::cin >> x >> y >> d >> c;
tmp.push_back({x, y, d, c});
}
for (int i = 0; i < Q; i++) {
int x, y;
std::cin >> x >> y;
P.push_back(point{x, y, 0});
}
kdt t(P);
for (auto [x, y, d, c] : tmp) {
t.apply_rectangle(x, x + d + 1, y, y + d + 1, c);
}
for (int i = 0; i < Q; i++) {
std::cout << t.get(i) << '\n';
}
}
Submission Info
Submission Time
2025-01-17 02:08:31+0900
Task
N - Building Construction
User
tonegawa
Language
C++ 23 (gcc 12.2)
Score
6
Code Size
7165 Byte
Status
AC
Exec Time
1060 ms
Memory
21048 KiB
Compile Error
Main.cpp: In function ‘constexpr int bit_ceil_log(unsigned int)’:
Main.cpp:9:21: warning: comparison of integer expressions of different signedness: ‘int’ and ‘unsigned int’ [-Wsign-compare]
9 | while ((1 << x) < (unsigned int)(n)) x++;
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
6 / 6
Status
Set Name
Test Cases
Sample
s1.txt, s2.txt, s3.txt
All
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, s1.txt, s2.txt, s3.txt
Case Name
Status
Exec Time
Memory
01.txt
AC 8 ms
3704 KiB
02.txt
AC 6 ms
4420 KiB
03.txt
AC 3 ms
3780 KiB
04.txt
AC 5 ms
3616 KiB
05.txt
AC 8 ms
4236 KiB
06.txt
AC 9 ms
3928 KiB
07.txt
AC 3 ms
3676 KiB
08.txt
AC 6 ms
3896 KiB
09.txt
AC 4 ms
3604 KiB
10.txt
AC 12 ms
4332 KiB
11.txt
AC 437 ms
20884 KiB
12.txt
AC 430 ms
20884 KiB
13.txt
AC 426 ms
21048 KiB
14.txt
AC 448 ms
20980 KiB
15.txt
AC 1060 ms
21048 KiB
16.txt
AC 1040 ms
21040 KiB
17.txt
AC 1031 ms
20944 KiB
18.txt
AC 1013 ms
20964 KiB
s1.txt
AC 1 ms
3516 KiB
s2.txt
AC 1 ms
3440 KiB
s3.txt
AC 1 ms
3444 KiB