QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#825061#9774. Same Sumucup-team5319#TL 1ms5688kbC++143.1kb2024-12-21 17:12:042024-12-21 17:12:04

Judging History

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

  • [2025-01-11 11:59:18]
  • hack成功,自动添加数据
  • (/hack/1443)
  • [2024-12-23 17:02:06]
  • hack成功,自动添加数据
  • (/hack/1310)
  • [2024-12-23 16:48:26]
  • hack成功,自动添加数据
  • (/hack/1309)
  • [2024-12-23 16:33:45]
  • hack成功,自动添加数据
  • (/hack/1308)
  • [2024-12-23 16:23:53]
  • hack成功,自动添加数据
  • (/hack/1307)
  • [2024-12-23 16:13:08]
  • hack成功,自动添加数据
  • (/hack/1306)
  • [2024-12-23 15:54:42]
  • hack成功,自动添加数据
  • (/hack/1305)
  • [2024-12-23 14:58:39]
  • hack成功,自动添加数据
  • (/hack/1304)
  • [2024-12-23 09:58:11]
  • hack成功,自动添加数据
  • (/hack/1302)
  • [2024-12-23 09:47:22]
  • hack成功,自动添加数据
  • (/hack/1301)
  • [2024-12-23 09:41:23]
  • hack成功,自动添加数据
  • (/hack/1300)
  • [2024-12-23 09:26:32]
  • hack成功,自动添加数据
  • (/hack/1299)
  • [2024-12-23 09:19:58]
  • hack成功,自动添加数据
  • (/hack/1298)
  • [2024-12-23 09:13:29]
  • hack成功,自动添加数据
  • (/hack/1297)
  • [2024-12-22 18:52:18]
  • hack成功,自动添加数据
  • (/hack/1296)
  • [2024-12-22 18:13:14]
  • hack成功,自动添加数据
  • (/hack/1294)
  • [2024-12-21 17:12:04]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:5688kb
  • [2024-12-21 17:12:04]
  • 提交

answer

//Linkwish's code
#include<bits/stdc++.h>
#define endl '\n'
#define si inline
#define fi first
#define se second
using namespace std;
typedef long long ll;typedef __int128 li;typedef long double ld;
typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef const int ci;typedef const ll cl;ci iinf=INT_MAX;cl linf=LLONG_MAX;
template<typename T>si bool gmax(T &x,const T y){if(x<y)return x=y,1;return 0;}
template<typename T>si bool gmin(T &x,const T y){if(y<x)return x=y,1;return 0;}

namespace LinkWish{

	ci N=200005,B=8;

	ci mod=1000000009;

	int c[B][B];

	int n,m;
	int a[N];

	struct T{
		int v[B];
		ll mx,mn,tag;
	}t[N<<2];
	si int ls(int x){return x<<1;}
	si int rs(int x){return x<<1|1;}
	si void push_up(int x){
		int lc=ls(x),rc=rs(x);
		for(int i=0;i<B;i++)t[x].v[i]=(t[lc].v[i]+t[rc].v[i])%mod;
		t[x].mx=max(t[lc].mx,t[rc].mx),t[x].mn=min(t[lc].mn,t[rc].mn);
	}
	si void update(int x,ll v){
		int mv=v%mod;
		for(int i=B-1;~i;i--){
			int res=0,pw=1;
			for(int j=0;j<=i;j++,pw=1ll*pw*mv%mod){
				(res+=1ll*t[x].v[i-j]*c[i][j]%mod*pw%mod)%=mod;
			}
			t[x].v[i]=res;
		}

		t[x].mn+=v,t[x].mx+=v,t[x].tag+=v;
	}
	si void push_down(int x){
		if(t[x].tag!=0){
			update(ls(x),t[x].tag);
			update(rs(x),t[x].tag);
			t[x].tag=0;
		}
	}
	void build(int x,int l,int r){
		if(l==r){
			for(int i=0,pw=1;i<B;i++,pw=1ll*pw*a[l]%mod)t[x].v[i]=pw;
			t[x].mn=t[x].mx=a[l];
			return ;
		}
		int mid=(l+r)>>1;
		build(ls(x),l,mid),build(rs(x),mid+1,r);
		push_up(x);
	}
	void modify(int x,int l,int r,int L,int R,int v){
		if(l>=L&&r<=R)return update(x,v);
		push_down(x);
		int mid=(l+r)>>1;
		if(L<=mid)modify(ls(x),l,mid,L,R,v);
		if(R>mid)modify(rs(x),mid+1,r,L,R,v);
		push_up(x);
	}

	int res[B];
	ll Mx,Mn;
	void ask(int x,int l,int r,int L,int R){
		if(l>=L&&r<=R){
			for(int i=0;i<B;i++)(res[i]+=t[x].v[i])%=mod;
			gmax(Mx,t[x].mx),gmin(Mn,t[x].mn);
			return ;
		}
		push_down(x);
		int mid=(l+r)>>1;
		if(L<=mid)ask(ls(x),l,mid,L,R);
		if(R>mid)ask(rs(x),mid+1,r,L,R);
	}
	
	void mian(){
		for(int i=0,j;i<B;i++)
			for(c[i][0]=j=1;j<=i;j++)
				c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
		
		cin>>n>>m;
		for(int i=1;i<=n;i++)cin>>a[i],a[i]<<=1;

		build(1,1,n);
		while(m--){
			int op,l,r,v;
			cin>>op>>l>>r;
			if(op==1){
				cin>>v,v<<=1;
				modify(1,1,n,l,r,v);
			}
			else{
				memset(res,0,sizeof res);
				Mx=0,Mn=linf,ask(1,1,n,l,r);
				int mid=mod-((Mx+Mn)>>1)%mod;
				for(int i=B-1;~i;i--){
					int rr=0,pw=1;
					for(int j=0;j<=i;j++,pw=1ll*pw*mid%mod){
						(rr+=1ll*c[i][j]*res[i-j]%mod*pw%mod)%=mod;
					}
					res[i]=rr;
				}

				bool flag=true;
				for(int i=1;i<B;i+=2){
					if(res[i]!=0){
						flag=false;
						break;
					}
				}

				//for(int i=0;i<B;i++)cout<<res[i]<<' ';
				//cout<<endl;

				if(flag)cout<<"Yes\n";
				else cout<<"No\n";
			}
		}
	}
}

signed main(){
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	#endif
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	LinkWish::mian();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5688kb

input:

8 4
1 2 3 4 5 6 7 8
2 1 8
1 1 4 4
2 1 6
2 1 8

output:

Yes
No
Yes

result:

ok 3 token(s): yes count is 2, no count is 1

Test #2:

score: -100
Time Limit Exceeded

input:

200000 200000
0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result: