QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#825061 | #9774. Same Sum | ucup-team5319# | TL | 1ms | 5688kb | C++14 | 3.1kb | 2024-12-21 17:12:04 | 2024-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]
- 提交
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 ...