QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#497802 | #6533. Traveling in Cells | Andycraft | WA | 206ms | 4072kb | C++14 | 4.6kb | 2024-07-29 18:10:45 | 2024-07-29 18:10:45 |
Judging History
answer
#define DEBUG 1
#define MULTI_TEST 1
#include <cassert>
#include <array>
#include <cstdio>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <chrono>
#include <random>
typedef long long LL;
typedef long double LF;
template <class T> using Arr = std::vector<T>;
template <class T> using Ptn = std::pair<T, T>;
const int MOD = 998244353;
const int INF = 0x3F3F3F3F;
#define MUL(u, v) (int)((LL)(u) * (v) % MOD)
inline int Pow(int a, int b) { int r = 1; for (; b > 0; b >>= 1, a = MUL(a, a)) if (b & 1) r = MUL(r, a); return r; }
inline int &Norm(int &x) { return x %= MOD; }
#define RNG(v) (v).begin(), (v).end()
#define FOR(i, s, t) for (int i = (s), i##_end = (t); i < i##_end; ++i)
#define ROF(i, s, t) for (int i = (s) - 1, i##_end = (t); i >= i##_end; --i)
template <class T>
void read(T &n) {
n = 0;
char ch;
bool flag = false;
do if ((ch = getchar()) == '-') flag = true;
while (ch < '0' || ch > '9');
for (; '0' <= ch && ch <= '9'; ch = getchar())
n = (n << 1) + (n << 3) + ch - '0';
if (flag)
n = -n;
}
int rand() {
static std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int r = (int)rng();
return r < 0 ? -r : r;
}
int rand(int l, int r) { return l + rand() % (r - l + 1); }
struct sum_seg_t {
int n;
Arr<LL> tr;
sum_seg_t(Arr<int> a) : n(a.size()), tr(2 * n) {
FOR(i, 0, n)
tr[n + i] = a[i];
for (int i = n - 1; i > 0; --i)
tr[i] = tr[i << 1] + tr[i << 1 | 1];
}
void modify(int p, int v) {
tr[p += n] = v;
for (p >>= 1; p > 0; p >>= 1)
tr[p] = tr[p << 1] + tr[p << 1 | 1];
}
LL sum(int l, int r) {
LL ans = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans += tr[l++];
if (r & 1) ans += tr[--r];
}
return ans;
}
};
// 线段树上倍增这么难写 ()
struct map_seg_t {
int n, sz;
typedef std::unordered_map<int, int> htable;
Arr<htable> tr;
htable merge(const htable &u, const htable &v) {
auto rt = u;
for (auto [x, c] : v)
rt[x] += c;
return rt;
}
map_seg_t(Arr<int> c) : n(c.size()) {
for (sz = 1; sz < n; sz <<= 1)
;
tr.resize(sz << 1);
FOR(i, 0, n)
tr[sz + i][c[i]] = 1;
ROF(i, sz, 1)
tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
}
void modify(int p, int c) {
auto it = tr[p += sz].begin();
int oldc = it->second;
tr[p].erase(it);
assert(tr[p].size() == 0);
tr[p][c] = 1;
for (p >>= 1; p > 0; p >>= 1) {
--tr[p][oldc];
++tr[p][c];
}
}
static int count_cell(const htable &map, const Arr<int> &v) {
int ans = 0;
for (auto c : v)
if (map.count(c))
ans += map.at(c);
return ans;
}
static inline int LB(int x) { return x & -x; }
static inline bool leftmost(int x) { return x == LB(x); }
static inline int prev_fa(int x) { return (x >> 1) - (~x & 1); }
static inline int prev_son(int x) { return (x << 1) - 1; }
static inline bool rightmost(int x) { return leftmost(x + 1); }
static inline int next_fa(int x) { return (x >> 1) + (x & 1); }
static inline int next_son(int x) { return (x << 1) + 2; }
int findl(int p, const Arr<int> &v) {
p += sz;
int h = 1;
do {
for (; p % 2 == 1 && p > 1; p >>= 1)
h <<= 1;
if (count_cell(tr[p], v) != h) {
while (p < sz) {
p = p * 2 + 1;
h >>= 1;
if (count_cell(tr[p], v) == h)
--p;
}
return p + 1 - sz;
}
--p;
} while (!rightmost(p));
return 0;
}
int findr(int p, const Arr<int> &v) {
p += sz;
int h = 1;
do {
for (; p % 2 == 0; p >>= 1)
h <<= 1;
if (count_cell(tr[p], v) != h) {
while (p < sz) {
p <<= 1;
h >>= 1;
if (count_cell(tr[p], v) == h)
++p;
}
return p - 1 - sz;
}
++p;
} while(p != (p & -p));
return n - 1;
}
};
void Solve() {
int n, q;
read(n); read(q);
Arr<int> c(n), v(n);
FOR(i, 0, n)
read(c[i]);
FOR(i, 0, n)
read(v[i]);
sum_seg_t sum_seg(v);
map_seg_t map_seg(c);
FOR(qq, 0, q) {
int op;
read(op);
if (op == 1) {
int p, x;
read(p); read(x);
map_seg.modify(p - 1, x);
} else if (op == 2) {
int p, x;
read(p); read(x);
sum_seg.modify(p - 1, x);
} else {
int x, k;
read(x); read(k);
--x;
Arr<int> v(k);
for (auto &x : v)
read(x);
int l = map_seg.findl(x, v);
int r = map_seg.findr(x, v);
// printf("[%d, %d] => %lld\n", l + 1, r + 1, sum_seg.sum(l, r + 1));
printf("%lld\n", sum_seg.sum(l, r + 1));
}
}
}
int main() {
int T;
#if MULTI_TEST
scanf("%d", &T);
#else
T = 1;
#endif
while (T--)
Solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4068kb
input:
2 5 10 1 2 3 1 2 1 10 100 1000 10000 3 3 1 3 3 3 2 2 3 2 5 20000 2 3 200 3 3 2 1 3 3 3 3 1 2 3 1 3 4 2 1 100000 1 2 2 3 1 2 1 2 4 1 1 2 3 4 1000000 1000000 1000000 1000000 3 4 4 1 2 3 4
output:
100 110 1200 21211 100010 4000000
result:
ok 6 numbers
Test #2:
score: -100
Wrong Answer
time: 206ms
memory: 4072kb
input:
20000 15 15 1 1 3 3 2 3 3 3 3 3 2 3 2 3 3 634593973 158136379 707704004 998369647 831633445 263092797 937841412 451774682 552617416 483763379 50360475 794662797 74247465 537217773 901809831 3 6 4 1 3 5 10 3 5 7 1 2 3 4 5 9 10 3 4 3 3 8 9 2 13 608033129 3 15 2 3 5 1 9 3 3 8 4 1 3 7 10 2 6 727472865 3...
output:
2689089686 8377825475 1706073651 1439027604 2689089686 792730352 8904867081 8904867081 8270273108 831633445 692051585 2782432626 697783016 883944422 184057757 696388752 184057757 287523250 184057757 3240862145 2667693025 2614711258 4006992373 1767091974 5348541057 5348541057 390631780 2290216252 942...
result:
wrong answer 16th numbers differ - expected: '287523250', found: '696388752'