QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#141337 | #6533. Traveling in Cells | cy1999 | WA | 1124ms | 46068kb | C++20 | 5.6kb | 2023-08-17 10:52:59 | 2023-08-17 10:53:02 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
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() ;t[p].cnt.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 ;
}
signed main() {
// freopen("data.in" , "r" , stdin) ;
// freopen("mine.out" , "w" , stdout) ;
cin >> T ;
while(T --) {
scanf("%lld%lld" , &n , &q) ;
for(int i = 1 ; i <= n ; i ++) scanf("%lld" , &c[i]) ;
for(int i = 1 ; i <= n ; i ++) scanf("%lld" , &v[i]) ;
seg.build(1 , 1 , n) ;
while(q --) {
int opt ; scanf("%lld" , &opt) ;
if(opt == 1) {
int p , x ; scanf("%lld%lld" , &p , &x) ;
seg.del(1 , 1 , n , p) ;
c[p] = x ; seg.add(1 , 1 , n , p) ;
} else if(opt == 2) {
int p , x ; scanf("%lld%lld" , &p , &x) ;
v[p] = x ; seg.change(1 , 1 , n , p) ;
} else {
int x ; scanf("%lld%lld" , &x , &k) ;
set<int> sa ;
for(int i = 1 ; i <= k ; i ++) {
scanf("%lld" , &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: 1ms
memory: 45276kb
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: 1124ms
memory: 46068kb
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 811735345 287523250 811735345 696388752 1494805791 1675459344 2667693025 2614711258 4006992373 1767091974 5348541057 5348541057 390631780 2290216252 94...
result:
wrong answer 15th numbers differ - expected: '184057757', found: '811735345'