QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#383532#6533. Traveling in Cellstjf4WA 143ms17708kbC++205.0kb2024-04-09 15:20:522024-04-09 15:20:53

Judging History

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

  • [2024-04-09 15:20:53]
  • 评测
  • 测评结果:WA
  • 用时:143ms
  • 内存:17708kb
  • [2024-04-09 15:20:52]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
const int inf=0x3f;
const int N=1e5+10;
ll n,m;
ll p[N],q[N],c[N];
int lowbit(int x) {
	return x&(-x);
}
void add(ll x,ll d) {
	for(int i=x;i<=n;i+=lowbit(i)) c[i]+=d;
}
ll qry(ll x) {
	ll res=0;
	for(int i=x;i>=1;i-=lowbit(i)) res+=c[i];
	return res;
}
ll ls[2][N],mp[N];
ll Tr[2][N<<4],up[2][N<<4];//两棵,区间赋值,区间求和 

void build(int rt,int l,int r,int op)
{
    if(l==r)
    {
        Tr[op][rt]=ls[op][l];
        return ;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid,op);
    build(rt<<1|1,mid+1,r,op);
    Tr[op][rt]=Tr[op][rt<<1]+Tr[op][rt<<1|1];
}

void push_down(int rt,int l,int r,int op)
{
    if(up[op][rt])
    {
        ll mid=(l+r)>>1;
        Tr[op][rt<<1]=up[op][rt]*(mid-l+1);
        Tr[op][rt<<1|1]=up[op][rt]*(r-mid);
        up[op][rt<<1]=up[op][rt];
        up[op][rt<<1|1]=up[op][rt];
        up[op][rt]=0;
    }
}

void update(int rt,int l,int r,int x,int y,ll val,int op)//将 [x,y] 内的数赋值成 val 
{
	if(up[op][rt]) push_down(rt,l,r,op);
    if(x<=l&&r<=y)
    {
   		Tr[op][rt]=val*(r-l+1);
       	up[op][rt]=val;
       	return ;
   	}
   	int mid=(l+r)>>1;
   	if(x<=mid) update(rt<<1,l,mid,x,y,val,op);
   	if(y>mid) update(rt<<1|1,mid+1,r,x,y,val,op);
   	Tr[op][rt]=Tr[op][rt<<1]+Tr[op][rt<<1|1];
}

ll query(int rt,int l,int r,int x,int y,int op)//求[x,y]的和 
{
	if(up[op][rt]) push_down(rt,l,r,op);
    if(x<=l&&r<=y) return Tr[op][rt];
    ll mid=(l+r)>>1,sum=0;
    if(x<=mid) sum+=query(rt<<1,l,mid,x,y,op);
    if(y>mid) sum+=query(rt<<1|1,mid+1,r,x,y,op);
    return sum;
}

void upd(int x,int y) {
	p[x]=y;
	if(n==1) return;
	if(x==1) {
		if(p[x]==p[x+1]) {
			int y1=query(1,1,n,x+1,x+1,1);
			if(x+1==n) y1=n+1;
			update(1,1,n,x,x,y1,1);//变点的右边 
			update(1,1,n,x+1,y1-1,0,0);//变点右边区间的左边 
		}
		else {
			int y1=query(1,1,n,x+1,x+1,1);
			if(x+1==n) y1=n+1;
			update(1,1,n,x,x,x+1,1);//变点的右边 
			update(1,1,n,x+1,y1-1,x,0);//变点右边区间的左边 
		}
	}
	else if(x==n) {
		if(p[x]==p[x-1]) {
			int x1=query(1,1,n,x-1,x-1,0);
			if(x-1==1) x1=0;
			update(1,1,n,x,x,x1,0);//变点的左边 
			update(1,1,n,x1+1,x-1,x+1,1);//变点左边区间的右边 
		}
		else {
			int x1=query(1,1,n,x-1,x-1,0);
			if(x-1==1) x1=0;
			update(1,1,n,x,x,x-1,0);//变点的左边 
			update(1,1,n,x1+1,x-1,x,1);//变点左边区间的右边 
		}
	}
	else if(p[x]!=p[x-1]&&p[x]!=p[x+1]) {
		int y1=query(1,1,n,x+1,x+1,1);
		int x1=query(1,1,n,x-1,x-1,0);
		update(1,1,n,x1+1,x-1,x,1);
		update(1,1,n,x+1,y1-1,x,0);
		update(1,1,n,x,x,x-1,0);
		update(1,1,n,x,x,x+1,1);
	}
	else if(p[x]==p[x-1]&&p[x]==p[x+1]) {
		int y1=query(1,1,n,x+1,x+1,1);
		int x1=query(1,1,n,x-1,x-1,0);
		update(1,1,n,x1+1,x-1,y1,1);
		update(1,1,n,x+1,y1-1,x1,0);
		update(1,1,n,x,x,x1,0);
		update(1,1,n,x,x,y1,1);
	}
	else if(p[x]==p[x-1]) {
		int y1=query(1,1,n,x+1,x+1,1);
		int x1=query(1,1,n,x-1,x-1,0);
		update(1,1,n,x1+1,x-1,x+1,1);
		update(1,1,n,x+1,y1-1,x,0);
		update(1,1,n,x,x,x1,0);
		update(1,1,n,x,x,x+1,1);
	}
	else if(p[x]==p[x+1]) {
		int y1=query(1,1,n,x+1,x+1,1);
		int x1=query(1,1,n,x-1,x-1,0);
		update(1,1,n,x1+1,x-1,x,1);
		update(1,1,n,x+1,y1-1,x-1,0);
		update(1,1,n,x,x,x-1,0);
		update(1,1,n,x,x,y1,1);
	}
}
void init() {
	for(int i=0;i<=n+1;i++) {
		c[i]=p[i]=q[i]=0;
		ls[0][i]=ls[1][i]=0;
	}
	for(int i=0;i<=(n<<4)+5;i++) {
		Tr[0][i]=Tr[1][i]=0;
		up[0][i]=up[1][i]=0;
	}
}
signed main() {
	IOS
	int t;
	cin>>t;
	vi ans;
	int sz=0;
	while(t--) {
		cin>>n>>m;
		init();
		for(int i=1;i<=n;i++) cin>>p[i];
		for(int i=1;i<=n;i++) {
			cin>>q[i]; add(i,q[i]);
		}
		for(int i=1;i<=n;i++) {
			if(i==1||p[i]!=p[i-1]) ls[0][i]=i-1;
			else ls[0][i]=ls[0][i-1];
		}
		for(int i=n;i>=1;i--) {
			if(i==n||p[i]!=p[i+1]) ls[1][i]=i+1;
			else ls[1][i]=ls[1][i+1];
		}
		build(1,1,n,0);
		build(1,1,n,1);
		while(m--) {
			int op; cin>>op;
			if(op==2) {
				int x,y; cin>>x>>y;
				add(x,-q[x]);
				add(x,y); q[x]=y;
			}
			else if(op==1) {
				int x,y; cin>>x>>y;
				upd(x,y);
			}
			else if(op==3) {
				vi g;
				int now,k; cin>>now>>k;
				for(int i=1;i<=k;i++) {
					int x; cin>>x;
					g.push_back(x); mp[x]=1;
				}
				int l=now,r=now;
				while(l&&mp[p[l]]) l=query(1,1,n,l,l,0); l++;
				while(r<=n&&mp[p[r]]) r=query(1,1,n,r,r,1); r--;
//				cout<<qry(r)-qry(l-1)<<'\n';
				ans.push_back(qry(r)-qry(l-1));
				if(++sz==193) {
					for(int i=1;i<=n;i++) cout<<p[i]<<' ';
					cout<<endl;
					for(int i=1;i<=n;i++) cout<<query(1,1,n,i,i,0)<<' ';
					cout<<endl;
					for(int i=1;i<=n;i++) cout<<query(1,1,n,i,i,1)<<' ';
					cout<<endl;
				}
				for(auto i:g) mp[i]=0;
			}
		}
	}
	for(auto i:ans) cout<<i<<endl;
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 13808kb

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: 143ms
memory: 17708kb

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:

3 3 3 3 3 3 3 3 2 3 3 3 3 3 2 
0 0 1 1 1 1 1 1 8 9 9 9 9 9 14 
15 9 9 9 9 9 9 9 10 15 15 15 15 15 16 
2689089686
8377825475
1706073651
1439027604
2689089686
792730352
8904867081
8904867081
8270273108
831633445
692051585
2782432626
697783016
883944422
184057757
287523250
184057757
696388752
184057757...

result:

wrong answer 1st numbers differ - expected: '2689089686', found: '3'