QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#398454 | #6533. Traveling in Cells | iwew | TL | 0ms | 8248kb | C++20 | 4.1kb | 2024-04-25 12:43:01 | 2024-04-25 12:43:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
struct Node {
int l, r;
ll v;
}tr[N << 2];
set<pair<int, int>> s[N];
void build(int u, int l, int r, vector<int> &v) {
if(l == r) {
tr[u] = {l, r, v[l]};
} else {
tr[u] = {l, r};
int mid = (l + r) >> 1;
build(u << 1, l, mid, v), build(u << 1 | 1, mid + 1, r, v);
tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}
}
void update(int u, int x, int v) {
if(tr[u].l == tr[u].r) {
tr[u].v = v;
} else {
int mid = (tr[u].l + tr[u].r) >> 1;
if(x <= mid) update(u << 1, x, v);
else update(u << 1 | 1, x, v);
tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}
}
ll query(int u, int l, int r) {
if(l <= tr[u].l && tr[u].r <= r) {
return tr[u].v;
} else {
ll res = 0;
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid) res += query(u << 1, l, r);
if(r > mid) res += query(u << 1 | 1, l, r);
return res;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T -- ) {
int n, q;
cin >> n >> q;
vector<int> c(n + 1), v(n + 1);
for(int i = 1; i <= n; i ++ ) cin >> c[i];
for(int i = 1; i <= n; i ++ ) cin >> v[i];
build(1, 1, n, v);
for(int i = 1; i <= n; i ++ ) s[c[i]].clear();
for(int i = 1; i <= n; i ++ ) {
int j = i;
while(j + 1 <= n && c[j + 1] == c[i]) j += 1;
s[c[i]].insert({i, j});
i = j;
}
while(q -- ) {
int type;
cin >> type;
if(type == 1) {
int p, x;
cin >> p >> x;
if(c[p] == x) continue;
auto cur = s[c[p]].upper_bound({p, p});
cur -- ;
auto [L, R] = *cur;
s[c[p]].erase(cur);
if(p - 1 >= L) s[c[p]].insert({L, p - 1});
if(p + 1 <= R) s[c[p]].insert({p + 1, R});
c[p] = x;
s[c[p]].insert({x, x});
if(p - 1 >= 1 && c[p - 1] == c[p]) {
cur = s[c[p - 1]].upper_bound({p - 1, p - 1});
cur -- ;
auto now = s[c[p]].upper_bound({p, p});
now -- ;
auto [l1, r1] = *cur;
auto [l2, r2] = *now;
s[c[p - 1]].erase(cur), s[c[p]].erase(now);
s[c[p]].insert({l1, r2});
}
if(p + 1 <= n && c[p + 1] == c[p]) {
cur = s[c[p + 1]].upper_bound({p + 1, p + 1});
cur -- ;
auto now = s[c[p]].upper_bound({p, p});
now -- ;
auto [l1, r1] = *now;
auto [l2, r2] = *cur;
s[c[p + 1]].erase(cur), s[c[p]].erase(now);
s[c[p]].insert({l1, r2});
}
} else if(type == 2) {
int p, x;
cin >> p >> x;
update(1, p, x);
} else {
int x, k;
cin >> x >> k;
set<int> sa;
for(int i = 0; i < k; i ++ ) {
int a;
cin >> a;
sa.insert(a);
}
int L = x, R = x;
while(sa.count(c[L])) {
auto cur = s[c[L]].upper_bound({L, L});
cur -- ;
auto [l, r] = *cur;
L = l - 1;
if(L == 0) break;
}
while(sa.count(c[R])) {
auto cur = s[c[R]].upper_bound({R, R});
cur -- ;
auto [l, r] = *cur;
R = r + 1;
if(R == n + 1) break;
}
cout << query(1, L + 1, R - 1) << '\n';
}
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 8248kb
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
Time Limit Exceeded
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...