QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#474111#6533. Traveling in CellszzisjtuRE 1610ms6968kbC++233.5kb2024-07-12 16:10:272024-07-12 16:10:28

Judging History

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

  • [2024-07-12 16:10:28]
  • 评测
  • 测评结果:RE
  • 用时:1610ms
  • 内存:6968kb
  • [2024-07-12 16:10:27]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define all(x) x.begin(), x.end()
#define lowbit(i) ((i)&(-i))
#define pii pair<int,int>
#define endl '\n'
#define mk(x,y) make_pair(x,y)
#define popcount(x) __builtin_popcount(x)
#define LF(x) fixed<<setprecision(x)
const double pi=3.14159265358979323846;
const double eps=1e-9;
const int inf=1e9;
const long long INF=4e18;
const int mod=1e9+7;
using namespace std;
const int N=1e5+10;
struct Seg
{
    int l,r;
    int val;
}seg[N*4];
int root[N];
int n,q,tot;
ll a[N],col[N];
int S[N];
void init(){
	for(int i=1;i<=n;i++){
		root[i]=0;
	}
	for(int i=1;i<=tot;i++){
		seg[i].l=seg[i].r=seg[i].val=0;
	}
	tot=0;

}

struct Tree_array
{
	int n;
	vector<ll>tr;
	Tree_array(int n_){
		n=n_;
		tr.assign(n+1,0);
	}
	//a为原数组 add(i,a[i]);
	void add(int x,int k){
		for(int i=x;i<=n;i+=lowbit(i)){
			tr[i]+=k;
		}
	}
	ll sum(int x){// 1-x的前缀和
		ll ans=0;
		for(int i=x;i;i-=lowbit(i)){
			ans+=tr[i];
		}
		return ans;
	}
	ll range_sum(int l,int r){
		return sum(r)-sum(l-1);
	}
};
void update(int p){
    seg[p].val=seg[seg[p].l].val+seg[seg[p].r].val;
}
//change(root[col[i]],1,n,x,val);//注意:单点加
void change(int &p,int l,int r,int x,int val){
    if(!p)p=++tot;
    if(l==r){
        seg[p].val+=val;
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid)change(seg[p].l,l,mid,x,val);
    else change(seg[p].r,mid+1,r,x,val);
    update(p);
}
//query(root[x],1,n,l,r);
auto query(int p,int l,int r,int L,int R){
    if(!p)return 0;
    if(L<=l&&R>=r)return seg[p].val;
    int mid=(l+r)/2;
    int res=0;
    if(L<=mid)res+=query(seg[p].l,l,mid,L,R);
    if(R>mid)res+=query(seg[p].r,mid+1,r,L,R);
    return res;
}
void solve()
{
    cin>>n>>q;
    Tree_array t(n);
    for(int i=1;i<=n;i++){
    	cin>>col[i];
    	change(root[col[i]],1,n,i,1);
    }
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	t.add(i,a[i]);
    }
    auto check=[&](int l,int r,int k){
    	int cnt=0;
    	for(int i=1;i<=k;i++){
    		cnt+=query(root[S[i]],1,n,l,r);
    	}
    	return cnt==r-l+1;
    };
    // cout<<1<<endl;
    while(q--){
    	int op;cin>>op;
    	if(op==1){
    		int x,val;
    		cin>>x>>val;
    		// for(int i=1;i<=n;i++){
    		// 	cout<<col[i]<<" \n"[i==n];
    		// }
    		change(root[col[x]],1,n,x,-1);
    		change(root[val],1,n,x,1);
    		col[x]=val;
    		// cout<<"change\n";
    		// for(int i=1;i<=n;i++){
    		// 	cout<<col[i]<<" \n"[i==n];
    		// }
    		// cout<<endl;
    	}
    	else if(op==2){
    		int x,val;
    		cin>>x>>val;
    		// for(int i=1;i<=n;i++){
    		// 	cout<<a[i]<<" \n"[i==n];
    		// }
    		t.add(x,val-a[x]);
    		a[x]=val;
    		// cout<<"change\n";
    		// for(int i=1;i<=n;i++){
    		// 	cout<<a[i]<<" \n"[i==n];
    		// }
    		// cout<<endl;
    	}
    	else if(op==3){
    		int x,k;
    		cin>>x>>k;
    		for(int i=1;i<=k;i++){
    			cin>>S[i];
    		}
    		//find_left
    		int l=0,r=x;
    		while(l<r){
    			int mid=(l+r)/2;
    			if(check(mid,x-1,k))r=mid;
    			else l=mid+1;
    		}
    		ll ans=t.range_sum(r,x);
    		//find_right
    		l=x,r=n;
    		while(l<r){
    			int mid=(l+r+1)/2;
    			if(check(x+1,mid,k))l=mid;
    			else r=mid-1;
    		}
    		ans+=t.range_sum(x+1,l);
    		cout<<ans<<endl;
    	}
    }
    init();
}

int 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: 1ms
memory: 5648kb

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: 0
Accepted
time: 201ms
memory: 5840kb

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:

ok 200062 numbers

Test #3:

score: 0
Accepted
time: 477ms
memory: 5684kb

input:

2000
150 150
8 3 8 8 8 6 8 4 2 7 6 8 8 5 8 7 7 8 5 6 8 8 6 8 8 8 8 7 8 6 6 8 8 8 6 2 3 4 8 8 7 8 5 8 2 6 8 7 8 8 6 8 6 8 3 8 8 8 8 4 7 8 7 3 7 6 7 5 5 8 6 8 8 6 3 8 6 7 6 8 8 7 4 8 6 7 8 7 7 7 7 8 8 8 8 2 5 2 8 8 6 7 6 3 8 8 7 8 8 8 6 6 8 6 6 7 5 8 8 8 7 8 7 7 6 8 8 8 8 8 8 6 5 7 5 5 8 7 8 7 7 7 6 5...

output:

4449391171
3290849667
852793841
5178673994
995994209
11431868919
4327723427
5071541023
3032743466
962345334
2997656427
4534278452
3851900075
3611231417
5071541023
1477584218
1299005818
1299005818
2145605244
854143763
886347565
2081234124
2333808475
2455955801
4179722063
2328504333
1473735464
4107685...

result:

ok 199987 numbers

Test #4:

score: 0
Accepted
time: 1610ms
memory: 6968kb

input:

10
30000 30000
3 4 2 4 4 4 4 3 4 3 4 3 4 3 4 4 2 4 4 4 4 4 3 3 3 4 3 4 3 4 3 3 4 2 4 3 3 3 3 4 3 4 4 4 4 2 3 3 4 2 3 4 4 4 4 1 4 4 4 4 4 4 4 4 3 3 3 4 4 4 4 4 2 3 4 4 4 4 3 4 4 3 3 3 4 4 3 4 4 2 3 4 4 4 4 3 2 4 3 4 3 2 4 4 3 4 2 2 4 4 4 4 2 4 3 2 4 4 3 4 4 4 2 4 4 3 2 3 2 3 3 3 4 2 4 3 4 1 4 3 4 4 4...

output:

6959437173
934970676
72461245502
8365928740
8384151048
984567228
12482909122
1904927816
15134139942
3759040688
92670874909
332468911
5936663371
3562978848
1300592004
10314009201
5581540905
131246926443
15087184135864
4077066271
1124704817
1520626740
4388174158
744377942
2770411457
6231852240
1508724...

result:

ok 200135 numbers

Test #5:

score: -100
Runtime Error

input:

3
100000 100000
6 6 2 6 5 3 6 5 4 6 4 6 6 6 6 5 2 5 2 6 6 6 1 6 5 6 4 5 6 6 5 4 5 4 3 4 5 5 6 6 5 6 6 5 2 5 6 5 4 2 5 6 6 6 5 2 5 6 6 4 5 6 3 3 6 5 6 5 5 5 5 4 4 4 4 3 6 5 4 5 6 5 6 6 6 6 3 6 5 6 5 4 3 5 6 4 5 3 6 5 3 5 6 4 6 5 4 5 5 5 2 5 4 6 6 3 5 5 5 5 5 4 5 5 6 5 5 6 6 6 5 5 4 6 5 4 4 2 6 6 6 5 ...

output:

753014823
938372065
5655899645
168297301
14372254310
1066586326
3520855082
2591792266
2321844837
64378192092
250581310
1845085639
1402247975
198007248
2157074263
2743531397
3433471688
10332600792
1085086491
4845484125
50019185900042
4036199358
154762798
50019185900042
1221387905
11240790307
10537215...

result: