QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#141290#6533. Traveling in Cellscy1999WA 2338ms45368kbC++205.4kb2023-08-17 10:21:382023-08-17 10:21:40

Judging History

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

  • [2023-08-17 10:21:40]
  • 评测
  • 测评结果:WA
  • 用时:2338ms
  • 内存:45368kb
  • [2023-08-17 10:21:38]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std ;

typedef long long ll ;
const int N = 100010 ;
int n , q , T  , k;
int c[N] , v[N] , a[N] ;
bool tag ;

struct SGTt {
    #define ls p*2
    #define rs p*2+1
    struct tree {
        set<int> s ;
        map<int , int> cnt ;
        ll sum ;
    } t[N * 4] ;
    set<int> merge(set<int> x , set<int> y ) {
        if(x.size() > y.size()) {
            auto it = y.begin() ; for( ; it != y.end() ; it ++ ) {
                x.insert(*it) ;
            }
            return x ;
        } else {
            auto it = x.begin() ;
            for( ; it != x.end() ; it ++) {
                y.insert(*it) ;
            }
            return y ;
        }
    }
    void pushup(tree &p , tree x , tree y) {
        if(x.s.size() > y.s.size()) {
            auto it = y.s.begin() ; for( ; it != y.s.end() ; it ++ ) {
                x.s.insert(*it) ; x.cnt[*it] += y.cnt[*it] ;
            }
            p = x ;
        } else {
            auto it = x.s.begin() ;
            for( ; it != x.s.end() ; it ++) {
                y.s.insert(*it) ;x.cnt[*it] += y.cnt[*it] ;
            }
            p = y ;
        }
        p.sum = x.sum + y.sum ;
    }
    void build(int p , int l , int r) {
        t[p].s.clear() ;
        if(l == r) {
            t[p].s.insert(c[l]) ;t[p].cnt[c[l]] = 1 ;
            t[p].sum = v[l] ;
            return ; 
        }
        int mid = (l + r) >> 1 ;
        build(ls , l , mid) ; build(rs , mid + 1 , r) ;
        pushup(t[p] , t[ls] , t[rs]) ;
    }
    tree query(int p , int l , int r , int ql , int qr){
        tree res ;
        if(tag) return res ;
        if(ql <= l && r <= qr) {
            return t[p] ;
        }
        int mid = (l + r) >> 1 ;
        if(ql > mid) return query(rs , mid + 1 , r , ql , qr) ;
        if(qr <= mid) return query(ls , l , mid , ql , qr) ;
        tree res1 = query(ls , l , mid , ql , qr) , res2 = query(rs , mid + 1 , r , ql , qr) ;
        pushup(res , res1 , res2) ;
        if(res.s.size() > k) {
            tag = 1 ;
        }
        return res ;
    }
    void ERASE(tree &p , int cx) {
        p.cnt[cx] -- ;
        if(p.cnt[cx] == 0) {
            p.cnt.erase(cx) ;
            p.s.erase(cx) ;
        }
    }
    void del(int p , int l , int r , int x) {
        ERASE(t[p] , c[x]) ;
        if(l == r) {
            return ;
        }
        int mid = (l + r) >> 1 ;
        if(x <= mid) {
            del(ls , l , mid , x) ;
        } else {
            del(rs , mid + 1 , r , x) ;
        }
    }
    void ADD(tree &p , int cx) {
        p.cnt[cx] ++ ;
        p.s.insert(cx) ;
    }
    void add(int p , int l , int r , int x) {
        ADD(t[p] , c[x]) ;
        if(l == r) return ;
        int mid = (l + r) >> 1 ;
        if(x <= mid) add(ls , l , mid , x) ;
        else add(rs , mid + 1 , r , x) ;
    }
    void change(int p , int l , int r , int x) {
        if(l == r) {
            t[p].sum = v[x] ;
            return ; 
        }
        int mid = (l + r) >> 1;
        if(x <= mid) change(ls , l , mid , x) ;
        else change(rs , mid + 1 , r , x ) ;
        t[p].sum = t[ls].sum + t[rs].sum ;
    }
    ll ask(int p , int l , int r , int ql , int qr) {
        if(ql <= l && r <= qr) {
            return t[p].sum ;
        }
        ll res = 0 ; int mid = (l + r) >> 1 ;
        if(ql <= mid) res += ask(ls , l , mid , ql , qr);
        if(qr > mid) res += ask(rs , mid + 1 , r , ql , qr) ;
        return res ;
    }
    tree res ;
} seg ;

bool check(set<int> x , set<int> y) {
    auto it = x.begin() ;
    for( ; it != x.end() ; it ++) {
        if(y.find(*it) == y.end()) return 0 ;
    }
    return 1 ;
}


int main() {
    cin >> T ;
    while(T --) {
        scanf("%d%d" , &n , &q) ;
        for(int i = 1 ; i <= n ; i ++) scanf("%d" , &c[i]) ;
        for(int i = 1 ; i <= n ; i ++) scanf("%d" , &v[i]) ;
        seg.build(1 , 1 , n) ;
        while(q --) {
            int opt ; scanf("%d" , &opt) ;
            if(opt == 1) {
                int p , x ; scanf("%d%d" , &p , &x) ;
                seg.del(1 , 1 , n , x) ; 
                c[p] = x ; seg.add(1 , 1 , n , p) ;
            }  else if(opt == 2) {
                int p , x ; scanf("%d%d" , &p , &x) ;
                v[p] = x ; seg.change(1 , 1 , n , p) ; 
            } else {
                int x ;  scanf("%d%d" , &x , &k) ;
                set<int> sa ;
                for(int i = 1 ; i <= k ; i ++) {
                    scanf("%d" , &a[i]) ;
                    sa.insert(a[i]) ;
                }
                int posl , posr ;
                int l = x , r = n ;
                while(l < r) {
                    int mid = (l + r + 1) >> 1 ;
                    tag = 0 ; seg.res = seg.query(1 , 1 , n , x , mid) ;
                    if(tag == 0 && check(seg.res.s , sa)) l = mid ;
                    else r = mid - 1 ;
                }
                posr = l ;
                r = x , l = 1 ;
                while(l < r) {
                    int mid = (l + r) >> 1;
                    tag = 0 ; seg.res = seg.query(1 , 1 , n , mid , x) ;
                    if(tag == 0 && check(seg.res.s , sa)) r = mid ;
                    else l = mid + 1 ;
                }
                posl = l ;
                ll ans = seg.ask(1 , 1 , n , posl , posr) ;
                printf("%lld\n" , ans) ;
            }
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 44364kb

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: 2338ms
memory: 45368kb

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
3330437448
8904867081
8904867081
8112136729
2537707096
692051585
2782432626
1394171768
883944422
811735345
287523250
811735345
696388752
1429487763
1675459344
2667693025
2614711258
4006992373
1767091974
5348541057
5348541057
390631780
2290216252...

result:

wrong answer 6th numbers differ - expected: '792730352', found: '3330437448'