QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#497716#6533. Traveling in CellssiunkyoWA 356ms3644kbC++204.6kb2024-07-29 16:22:522024-07-29 16:22:53

Judging History

你现在查看的是最新测评结果

  • [2024-07-29 16:22:53]
  • 评测
  • 测评结果:WA
  • 用时:356ms
  • 内存:3644kb
  • [2024-07-29 16:22:52]
  • 提交

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'