Submission #974007

#	Time	Username	Problem	Language	Result	Execution time	Memory
974007		8pete8	Relativnost (COCI15_relativnost)	C++17	140 / 140	2636 ms	17740 KiB

relativnost

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
//#define int long long
//#define double long double
const int mod=10007,mxn=1e5+5,lg=60,inf=1e9,minf=-1e9,Mxn=1e6+50000;
int n,m;
struct node{
	int dp[22];
	node operator+(node a)const{
		node tmp;
		for(int i=0;i<=m;i++)tmp.dp[i]=0;
		for(int i=0;i<=m;i++)for(int j=0;j<=i;j++)tmp.dp[i]=(tmp.dp[i]+(a.dp[i-j]*dp[j])%mod)%mod;
		return tmp;
	}
	void init(){
		for(int i=0;i<=m;i++)dp[i]=0;
		dp[0]=1;
	}
	void print(){
		for(int i=0;i<=m;i++)cout<<dp[i]<<" ";
		cout<<'\n';
	}
};

struct seg{
	node v[2*mxn+10];
	void init(){for(int i=0;i<=2*n;i++)v[i].init();}
	void update(int pos,int a,int b){
		pos+=n;
		v[pos].init();
		v[pos].dp[0]=b;
		v[pos].dp[1]=a;
		for(int i=pos;i>0;i>>=1)v[i>>1]=v[i]+v[i^1];
	}
	//1 2 1 4
	//1 2 1 4
	int qry(int l=0,int r=n-1){
		node ans;
		ans.init();
		for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
			if(l&1)ans=(ans+v[l++]);
			if(!(r&1))ans=(ans+v[r--]);
		}
		int sum=0;
		for(int i=0;i<=m;i++)sum=(sum+ans.dp[i])%mod;
		return sum;
	}
}t;
int inverse(int a){
	int ex=mod-2,ans=1;
	while(ex){
		if(ex&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		ex>>=1;
	}
	return ans;
}
int bro[mxn+10],bro2[mxn+10];
int32_t main(){
	fastio
	//matrix segtree?
	cin>>n>>m;
	int ans=1;
	m--;
	for(int i=0;i<n;i++)cin>>bro[i];
	for(int i=0;i<n;i++){
		cin>>bro2[i];
		bro[i]%=mod;
		bro2[i]%=mod;
		t.update(i,bro[i],bro2[i]);
		ans=(ans*(bro[i]+bro2[i]))%mod;
	}
	int q;cin>>q;
	while(q--){
		int x,a,b;cin>>x>>a>>b;
		x--;
		ans=(ans*inverse(bro[x]+bro2[x]))%mod;
		a%=mod;
		b%=mod;
		bro[x]=a,bro2[x]=b;
		ans=(ans*(bro[x]+bro2[x]))%mod;
		t.update(x,a,b);
		int ra=(ans-t.qry()+mod)%mod;
		cout<<ra<<'\n';
	}
	return 0;
}
/*
1 2 3 1
*/

• Subtask 1: 140 / 140