QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#725966 | #6533. Traveling in Cells | He_ng | WA | 1ms | 3572kb | C++20 | 4.9kb | 2024-11-08 20:58:05 | 2024-11-08 20:58:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 1e6;
const int M = 2e3;
const int MAXA = 1e6 + 5;
template <typename T>
struct DynamicSegtree {
struct node {
T data, tag;
node *lc, *rc;
node(T data_ = 0) : data(data_), tag(0), lc(nullptr), rc(nullptr) {}
void up() {
data = 0;
if (lc != nullptr)
data += lc->data;
if (rc != nullptr)
data += rc->data;
return;
}
void down(int l, int r) {
if (lc == nullptr)
lc = new node;
if (rc == nullptr)
rc = new node;
int mid = l + r >> 1;
lc->data += (mid - l + 1) * tag;
lc->tag += tag;
rc->data += (r - mid) * tag;
rc->tag += tag;
tag = 0;
}
} *rt = new node(0);
void modify(node *rt, int L, int R, int l, int r, T val) {
if (l <= L && R <= r) {
rt->data += (R - L + 1) * val;
rt->tag += val;
return;
}
rt->down(L, R);
int mid = L + R >> 1;
if (l <= mid)
modify(rt->lc, L, mid, l, r, val);
if (r > mid)
modify(rt->rc, mid + 1, R, l, r, val);
rt->up();
return;
}
T query(node *rt, int L, int R, int l, int r) {
if (l <= L && R <= r) {
return rt->data;
}
rt->down(L, R);
int mid = L + R >> 1;
T ret{};
if (l <= mid)
ret += query(rt->lc, L, mid, l, r);
if (r > mid)
ret += query(rt->rc, mid + 1, R, l, r);
return ret;
}
};
int cc[N];
int n, q;
int lowbit(int x) { return x & -x; }
void add(int i, int x) {
while (i <= n) {
cc[i] += x;
i += lowbit(i);
}
}
int get(int i) {
int ans = 0;
while (i) {
ans += cc[i];
i -= lowbit(i);
}
return ans;
}
bool check(int x, vector<int> a(), int st) {
}
void solve() {
cin >> n >> q;
vector<DynamicSegtree<int>> tree(n + 1);
vector<int> c(n + 1);
vector<int> v(n + 1);
for (int i = 1; i <= n; i++) {
cin >> c[i];
tree[c[i]].modify(tree[c[i]].rt, 1, MAXA, i, i, 1);
cc[i] = 0;
}
for (int i = 1; i <= n; i++) {
cin >> v[i];
add(i, v[i]);
}
while (q--) {
int x;
cin >> x;
if (x == 1) {
int p, y;
cin >> p >> y;
tree[c[p]].modify(tree[c[p]].rt, 1, MAXA, p, p, -1);
tree[y].modify(tree[y].rt, 1, MAXA, p, p, 1);
c[p] = y;
}
if (x == 2) {
int p, y;
cin >> p >> y;
add(p, y - v[p]);
v[p] = y;
} else if (x == 3) {
int st, k;
cin >> st >> k;
vector<int> a(k + 1);
for (int i = 1; i <= k; i++) {
cin >> a[i];
}
int l = 1;
int r = st;
auto check1 = [&](int mid, const vector<int> &a, int st) -> bool {
int sum = 0;
for (int i = 1; i <= k; i++) {
int cnt = tree[a[i]].query(tree[a[i]].rt, 1, MAXA, mid, st);
sum += cnt;
}
if (sum == st - mid + 1)
return true;
return false;
};
auto check2 = [&](int mid, const vector<int> &a, int st) -> bool {
int sum = 0;
for (int i = 1; i <= k; i++) {
int cnt = tree[a[i]].query(tree[a[i]].rt, 1, MAXA, st, mid);
sum += cnt;
}
if (sum == mid - st + 1)
return true;
return false;
};
while (l < r) {
int mid = (l + r ) >> 1;
if (check1(mid, a, st))
r = mid;
else
l = mid + 1;
}
int ansl = l;
l = st;
r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check2(mid, a, st))
l = mid;
else
r = mid - 1;
}
int ansr = r;
cout << ansl << " " << ansr << " ";
cout << get(ansr) - get(ansl -1) << endl;
}
}
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
/*
1
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
*/
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3572kb
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:
3 3 100 2 3 110 3 4 1200 1 5 21211 1 2 100010 1 4 4000000
result:
wrong answer 1st numbers differ - expected: '100', found: '3'