結果

問題 No.510 二次漸化式
ユーザー 小夫
提出日時 2025-02-28 22:43:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,365 bytes
コンパイル時間 1,996 ms
コンパイル使用メモリ 176,852 KB
実行使用メモリ 814,848 KB
最終ジャッジ日時 2025-02-28 22:43:20
合計ジャッジ時間 4,063 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 1
other -- * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:100:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  100 |                 scanf(" %c",&op);
      |                 ~~~~~^~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<48||ch>57){if(ch=='-')f=-1;ch=getchar();}
	while(ch>=48&&ch<=57)x=(x<<1)+(x<<3)+(ch&15),ch=getchar();
	return x*f;
}
inline void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+48);
	return;
}
inline void openfile()
{
	freopen("16.in","r",stdin);
	freopen("generator.out","w",stdout);
}
constexpr int M=1e5+4,mod=1e9+7;
int X[M],Y[M];
struct Matrix
{
    int a[5][5];
    Matrix(){}
    inline void clear(){memset(a,0,sizeof a);}
    inline void init(int id)
	{
		a[1][1]=1,a[2][2]=Y[id],a[2][3]=2*Y[id]%mod;
		a[3][1]=X[id],a[3][3]=1ll*Y[id]*Y[id]%mod;
		a[4][2]=1,a[4][3]=1,a[4][4]=1;
		return;
	}
    inline Matrix operator*(const Matrix&b)const
	{
        Matrix res;
		res.clear();
        for(int k=1;k<=4;++k)
            for(int i=1;i<=4;++i)
                for(int j=1;j<=4;++j)
                    res.a[i][j]=(res.a[i][j]+1ll*a[i][k]*b.a[k][j]%mod)%mod;
        return res;
    }
    inline int value()
    {
    	int res=0;
    	for(int i=1;i<=4;++i)res=(res+a[i][1])%mod;
    	return res;
	}
};
struct SegmentTree
{
	#define lson rt<<1
	#define rson rt<<1|1
	Matrix tr[M<<2];
	inline void update(int rt){tr[rt]=tr[lson]*tr[rson];return;}
	inline void build(int rt,int l,int r)
	{
		if(l==r){tr[rt].init(l);return;}
		int mid=l+r>>1;
		build(lson,l,mid);
		build(rson,mid+1,r);
		update(rt);
		return;
	}
	inline void modify(int rt,int l,int r,int pos)
	{
		if(l==r){tr[rt].init(l);return;}
		int mid=l+r>>1;
		if(pos<=mid)modify(lson,l,mid,pos);
		if(pos>mid)modify(rson,mid+1,r,pos);
		update(rt);
		return;
	}
	inline Matrix query(int rt,int l,int r,int posl,int posr)
	{
		if(posl<=l&&r<=posr)return tr[rt];
		Matrix res;
		res.clear();
		for(int i=1;i<=4;++i)res.a[i][i]=1;
		int mid=l+r>>1;
		if(posl<=mid)res=res*query(lson,l,mid,posl,posr);
		if(posr>mid)res=res*query(rson,mid+1,r,posl,posr);
		return res;
	}
	#undef lson
	#undef rson
}T;
int main()
{
	//openfile();
	int n=read()+1,q=read();
	T.build(1,1,n);
	for(int i=1;i<=q;++i)
	{
		char op;
		scanf(" %c",&op);
		int id=read();
        if(op=='x')X[id+1]=read(),T.modify(1,1,n,id+1);
        if(op=='y')Y[id+1]=read(),T.modify(1,1,n,id+1);
		if(op=='a')
		{
			auto ans=T.query(1,1,n,1,id);
	        write(ans.value()),puts("");
		}
	}
	return 0;
}
0