QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#497716 | #6533. Traveling in Cells | siunkyo | WA | 356ms | 3644kb | C++20 | 4.6kb | 2024-07-29 16:22:52 | 2024-07-29 16:22:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ld long double
#define i64 __int128
#define PII pair<int,int>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
//cout<<setiosflags(ios::fixed)<<setprecision(K);
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
const double eps = 1e-9;
const double PI = acos(-1.0);
const int INF = 1e9 + 7;
const int mod = 998244353;
const int N = 1e5 + 10,M = 1e5;
int n, q;
int v[N], c[N];
int root[N], tot; // T[i]:颜色为i的线段树的根
struct node{
int ls, rs, sum;
}tr[N * 200];
void update(int& p, int loc, int k, int l = 1, int r = M){ // 对于该颜色更新点loc的价值+1
if(!p) p = ++ tot;
tr[p].sum += k;
if(l == r) return ;
int mid = (l + r) >> 1;
if(loc <= mid) update(tr[p].ls, loc, k, l, mid);
else update(tr[p].rs, loc, k, mid + 1, r);
}
int query(int p, int ql, int qr, int l = 1, int r = M){ // 对于颜色i查询区间[ql, qr]该颜色的个数
if(!p) return 0;
if(ql <= l && r <= qr) return tr[p].sum;
int mid = (l + r) >> 1, ans = 0;
if(ql <= mid) ans += query(tr[p].ls, ql, qr, l, mid);
if(qr > mid) ans += query(tr[p].rs, ql, qr, mid + 1, r);
return ans;
}
template <typename T>
struct Fenwick {
int n;
vector<T> a;
Fenwick(int n = 0) {init(n);}
void init(int n) { this->n = n; a.assign(n, T());}
//在x处加上v
void add(int x, T v) {
for (int i = x + 1; i <= n; i += i & -i) {
a[i - 1] += v;
}
}
//取[0.x)的和
T sum(int x) {
auto ans = T();
for (int i = x; i > 0; i -= i & -i) {
ans += a[i - 1];
}
return ans;
}
//取[l,r)的和
T rangeSum(int l, int r) {
return sum(r) - sum(l);
}
//取已插入的元素从小到大排序后第k个元素的值,这里从0开始记录
int kth(T k) {
int x = 0;
for (int i = 1 << __lg(n); i; i /= 2) {
if (x + i <= n && k >= a[x + i - 1]) {
x += i;
k -= a[x - 1];
}
}
return x;
}
};
//Fenwick<int> fen(N);
//fen.add(x,y); //往x位置加上y
//fen.sum(x+1); //求[0,x+1)的和
void init(){
for(int i = 0;i <= tot;i ++) tr[i] = {0,0,0};
for(int i = 1;i <= n;i ++) root[i] = 0;
tot = 0;
}
void solve(){
cin >> n >> q;
init();
vector<int> root(n + 1);
for(int i = 1;i <= n;i ++){
cin >> c[i];
update(root[c[i]],i,1);
}
Fenwick<LL> fen(n + 1);
for(int i = 1;i <= n;i ++){
cin >> v[i];
fen.add(i,v[i]);
}
while(q --){
int op;
cin >> op;
if(op == 1){
int p,x;
cin >> p >> x;
update(root[c[p]],p,-1);
c[p] = x;
update(root[c[p]],p,1);
}else if(op == 2){
int p,x;
cin >> p >> x;
fen.add(p,-v[p]);
fen.add(p,x);
}else{
int x,k;
cin >> x >> k;
vector<int> a(k + 1);
for(int i = 1;i <= k;i ++) cin >> a[i];
auto check = [&](int ll){
LL sum = 0;
for(int i = 1;i <= k;i ++){
sum += query(root[a[i]],ll,x);
}
if(sum == x - ll + 1) return true;
return false;
};
auto checkk = [&](int rr){
LL sum = 0;
for(int i = 1;i <= k;i ++){
sum += query(root[a[i]],x,rr);
}
if(sum == rr - x + 1) return true;
return false;
};
int l = 1,r = x,ansl = -1,ansr = -1;
while(l <= r){
int mid = (l + r) / 2;
if(check(mid) == true){
r = mid - 1;
ansl = mid;
}else{
l = mid + 1;
}
}
l = x,r = n;
while(l <= r){
int mid = (l + r) / 2;
if(checkk(mid) == true){
l = mid + 1;
ansr = mid;
}else{
r = mid - 1;
}
}
// cout << ansl << ' ' << ansr << endl;
cout << fen.rangeSum(ansl,ansr + 1) << endl;
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T = 1;
cin >> T;
while(T --){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
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: 356ms
memory: 3644kb
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 287523250 184057757 696388752 184057757 1675459344 2667693025 2614711258 4006992373 1767091974 5348541057 5348541057 390631780 2290216252 942...
result:
wrong answer 61st numbers differ - expected: '4024466864', found: '4401559292'