QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#419944 | #6533. Traveling in Cells | XiaoretaW | RE | 0ms | 0kb | C++20 | 3.0kb | 2024-05-24 12:57:18 | 2024-05-24 12:57:18 |
answer
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define rep(i, l, r) for (int i = l; i < r; ++i)
#define per(i, r, l) for (int i = r-1; i >= l; --i)
typedef long long ll;
typedef pair<int, int> PI;
template<typename T> bool setmax(T &a, T b) { return (a < b ? a = b, 1 : 0); }
template<typename T> bool setmin(T &a, T b) { return (a > b ? a = b, 1 : 0); }
// Set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Tree;
template<typename T> struct BIT {
int n;
vector<T> tr;
BIT(int _n) {
n = _n;
tr.resize(n+1);
}
T prefix(int i) {
T res = 0;
for (; i; i -= i&(-i)) res += tr[i];
return res;
}
T query(int l, int r) { return prefix(r) - prefix(l-1); }
void modify(int i, T val) { for (; i <= n; i += i&(-i)) tr[i] += val; }
};
Tree S[300010];
void solve() {
int n, q; cin >> n >> q;
vector<int> c(n + 1), v(n + 1);
BIT<ll> vbit(n);
for (int i = 1; i <= n; i++) {
cin >> c[i];
S[c[i]].insert(i);
}
for (int i = 1; i <= n; i++) {
cin >> v[i];
vbit.modify(i, v[i]);
}
while (q--) {
int t; cin >> t;
if (t == 1 || t == 2) {
int p, x; cin >> p >> x;
if (t == 1) {
S[c[p]].erase(p);
c[p] = x;
S[c[p]].insert(p);
} else {
vbit.modify(p, -v[p]);
v[p] = x;
vbit.modify(p, v[p]);
}
} else {
int x, k; cin >> x >> k;
vector<int> st(k);
for (int &i : st) cin >> i;
auto gao = [&](int f) {
auto ck = [&](int m) {
int tot = 0;
for (int color : st) {
auto get = [&](int ll, int rr) {
return S[color].order_of_key(rr + 1) - S[color].order_of_key(ll);
};
tot += f ? get(x - m + 1, x) : get(x, x + m - 1);
}
assert(tot <= m);
return tot == m;
};
int l = 1, r = f ? x : n - x + 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (ck(mid)) l = mid;
else r = mid - 1;
}
return l;
};
int L = x - gao(1) + 1, R = x + gao(0) - 1;
cout << vbit.query(L, R) << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int tt; cin >> tt;
while (tt--) solve();
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
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