QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#125702 | #6533. Traveling in Cells | definieren | WA | 1ms | 3488kb | C++14 | 3.6kb | 2023-07-17 13:06:58 | 2023-07-17 13:07:01 |
Judging History
answer
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef vector<int> vi;
typedef vector<pii> vpii;
template<typename T> T read() {
T x = 0; int f = 1; char ch = getchar();
while (ch < '0' || ch > '9') f = ((ch == '-') ? (~f + 1) : f), ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x * f;
}
const int MOD = 998244353;
template<typename T> T add(T a, T b) { return (a + b >= MOD) ? (a + b - MOD) : (a + b); }
template<typename T> T del(T a, T b) { return (a - b < 0) ? (a - b + MOD) : (a - b); }
template<typename T> T cadd(T &a, T b) { return a = add(a, b); }
template<typename T> T cdel(T &a, T b) { return a = del(a, b); }
template<typename T> T cmax(T &a, T b) { return a = max(a, b); }
template<typename T> T cmin(T &a, T b) { return a = min(a, b); }
bool Mbe;
const int MAXN = 1e5+9;
int n, q, c[MAXN], v[MAXN], a[MAXN];
ll bit[MAXN];
int rt[MAXN], cnt[MAXN], ls[MAXN], rs[MAXN], tot = 0;
void Update(int x, int k) {
for (; x <= n; x += x & -x)
bit[x] += k;
return;
}
ll Query(int x) {
ll ans = 0;
for (; x; x -= x & -x)
ans += bit[x];
return ans;
}
int New_Node() {
cnt[++tot] = ls[tot] = rs[tot] = 0;
return tot;
}
void Push_Up(int p) {
cnt[p] = cnt[ls[p]] + cnt[rs[p]];
return;
}
void Update(int &p, int pos, int w, int L = 1, int R = n) {
if (!p) p = New_Node();
if (L == R) {
cnt[p] += w;
return;
}
int Mid = L + R >> 1;
if (pos <= Mid) Update(ls[p], pos, w, L, Mid);
else Update(rs[p], pos, w, Mid + 1, R);
Push_Up(p); return;
}
int Query(int p, int l, int r, int L = 1, int R = n) {
if(!p) return 0;
if(l <= L && R <= r) return cnt[p];
int Mid = L + R >> 1, cnt = 0;
if (l <= Mid) cnt += Query(ls[p], l, r, L, Mid);
if (Mid < r) cnt += Query(rs[p], l, r, Mid + 1, R);
return cnt;
}
bool check(int l, int r, int k){
int ans = 0;
for (int i = 1; i <= k; i++)
ans += Query(rt[a[i]], l, r);
return ans == r - l + 1;
}
int Get_Left(int x, int k) {
int l = 1, r = x;
while (l < r) {
int mid = l + r >> 1;
if (check(mid, x, k)) r = mid;
else l = mid + 1;
}
return l;
}
int Get_Right(int x, int k) {
int l = x, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(x, mid, k)) l = mid;
else r = mid - 1;
}
return l;
}
void Clear() {
for (int i = 1; i <= n; i++)
bit[i] = 0ll, rt[i] = 0;
tot = 0; return;
}
bool Med;
int main() {
int T = read<int>();
while (T--) {
n = read<int>(), q = read<int>();
for (int i = 1; i <= n; i++)
c[i] = read<int>(), Update(rt[c[i]], i, 1);
for (int i = 1; i <= n; i++)
v[i] = read<int>(), Update(i, v[i]);
while (q--) {
int opt = read<int>();
if (opt == 1) {
int p = read<int>(), x = read<int>();
Update(rt[c[p]], p, -1), Update(rt[c[p] = x], p, 1);
} else if (opt == 2) {
int p = read<int>(), x = read<int>();
Update(p, -v[p]), v[p] = x, Update(p, v[p]);
} else {
int x = read<int>(), k = read<int>();
for (int i = 1; i <= k; i++)
a[i] = read<int>();
int l = Get_Left(x, k), r = Get_Right(x, k);
ll ans = Query(r) - Query(l - 1);
printf("%lld\n", ans);
}
}
Clear();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3488kb
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 1000000
result:
wrong answer 6th numbers differ - expected: '4000000', found: '1000000'