結果

問題 No.426 往復漸化式
ユーザー Guowen RongGuowen Rong
提出日時 2024-10-15 23:41:00
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,371 bytes
コンパイル時間 2,393 ms
コンパイル使用メモリ 176,264 KB
実行使用メモリ 113,152 KB
最終ジャッジ日時 2024-10-15 23:41:07
合計ジャッジ時間 7,223 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 74 ms
113,024 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(register int i=l;i<=r;i++)
#define _For(i,l,r) for(register int i=r;i>=l;i--)
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=1e5+10,M=3,mod=1e9+7;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
struct Matrix{
	ll n,m;
	ll a[M][M];
	Matrix(){memset(a,0,sizeof(a));}
	ll* operator[](ll x){
		return a[x];
	}
	void init(ll _n,ll _m,bool f=0){
		n=_n,m=_m;
		if(f){
			For(i,0,n-1)
			  a[i][i]=1;
		}
	}
	void Read(){
		For(i,0,n-1)
		  For(j,0,m-1)
		    a[i][j]=read();
	}
	friend Matrix operator+(Matrix a,Matrix b){
		Matrix ans;
		ans.init(a.n,a.m);
		For(i,0,a.n-1)
		  For(j,0,a.m-1)
		    ans[i][j]=a[i][j]+b[i][j];
		return ans;
	}
	friend Matrix operator*(Matrix a,Matrix b){ // (3,3),(3,1)
		Matrix ans;
		ans.n=a.n,ans.m=b.m;
		For(i,0,a.n-1)
		  For(j,0,b.m-1)
			For(k,0,a.m-1)
			  ans[i][j]=(ans[i][j]+a[i][k]*b[k][j]%mod)%mod;
		return ans;
	}
}A,B,_A,_B,Aans,Bans,BD,AD,SD;
ll n,q,x;
char op[3];
namespace Seg{
	struct Node{
		ll l,r;
		Matrix t1,t2,t3;
	}X[N<<2];
	void pushup(ll k){
		X[k].t1=X[k<<1|1].t1*X[k<<1].t1;
		X[k].t2=X[k<<1].t2*X[k<<1|1].t2;
		X[k].t3=X[k<<1].t3+X[k<<1].t2*X[k<<1|1].t3*X[k<<1].t1;
	}
	void build(ll k,ll l,ll r){
		X[k].l=l,X[k].r=r;
		X[k].t1.init(3,3,1);
		X[k].t2.init(2,2,1);
		X[k].t3.init(2,3);
		if(l==r){
			X[k].t3[0][0]=l*6;
			X[k].t3[0][1]=l*6+1;
			X[k].t3[0][2]=l*6+2;
			X[k].t3[1][0]=l*6+3;
			X[k].t3[1][1]=l*6+4;
			X[k].t3[1][2]=l*6+5;
			return ;
		}
		ll mid=(l+r)>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
	}
	void update(ll k,ll i,Matrix v,bool f){
//		cerr<<k<<':'<<X[k].l<<' '<<X[k].r<<'\n';
		if(X[k].l==i&&i==X[k].r){
			if(f)
			  X[k].t2=v;
			else
			  X[k].t1=v;
			return ;
		}
		ll mid=(X[k].l+X[k].r)>>1;
		if(i<=mid)
		  update(k<<1,i,v,f);
		else
		  update(k<<1|1,i,v,f);
		pushup(k);
	}
	Matrix query1(ll k,ll l,ll r){
//		puts("Yes1");
//		cerr<<k<<':'<<l<<' '<<r<<' '<<X[k].l<<' '<<X[k].r<<'\n';
		if(l>r||l<0)
		  return AD;
		if(X[k].l==l&&r==X[k].r)
		  return X[k].t1;
		ll mid=(X[k].l+X[k].r)>>1;
		if(r<=mid)
		  return query1(k<<1,l,r);
		else if(l>mid)
		  return query1(k<<1|1,l,r);
		else
		  return query1(k<<1|1,mid+1,r)*query1(k<<1,l,mid);
	}
	Node query3(ll k,ll l,ll r){
//		puts("Yes3");
		if(l>r||r>n)
		  return {0,0,AD,BD,SD};
		if(X[k].l==l&&r==X[k].r)
		  return X[k];
		ll mid=(X[k].l+X[k].r)>>1;
		if(r<=mid)
		  return query3(k<<1,l,r);
		else if(l>mid)
		  return query3(k<<1|1,l,r);
		else{
			Node ans;
			auto L=query3(k<<1,l,mid),R=query3(k<<1|1,mid+1,r);
			ans.t1=R.t1*L.t1;
			ans.t2=L.t2*R.t2;
			ans.t3=L.t3+L.t2*R.t3*L.t1;
			return ans;
		}
	}
};
bool End;
int main(){
//	open("A.in","A.out");
	AD.init(3,3,1),BD.init(2,2,1),SD.init(2,3,1);
	n=read();
	A.init(3,1),Aans.init(3,1),_A.init(3,3);
	A.Read();
	B.init(2,1),Bans.init(2,1),_B.init(2,2);
	B.Read();
	Seg::build(1,0,n);
	q=read();
	while(q--){
		scanf("%s",op);
		if(op[1]=='a'){
			x=read()-1;
			if(x<0)
			  Aans=A;
			else
			  Aans=Seg::query1(1,0,x)*A;
			write(Aans[0][0]);
			putchar(' ');
			write(Aans[1][0]);
			putchar(' ');
			write(Aans[2][0]);
			putchar('\n');			
		}
		else if(op[1]=='b'){
			x=read();
			if(x==n)
			  Bans=B;
			else{
				auto X=Seg::query3(1,x+1,n);
				auto Y=Seg::query1(1,0,x)*A;
				Bans=(X.t3*Y)+(X.t2*B);
			}
			write(Bans[0][0]);
			putchar(' ');
			write(Bans[1][0]);
			putchar('\n');
		}
		else if(op[0]=='a'){
			x=read();
			_A.Read();
			Seg::update(1,x,_A,0);		
		}
		else{
			x=read();
			_B.Read();
//			cerr<<x<<'\n';
			Seg::update(1,x,_B,1);
		}
	}
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}
0