제출 #95518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95518		ryansee	Relativnost (COCI15_relativnost)	C++14	140 / 140	3462 ms	30624 KiB

relativnost

#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF (long long) 1e18//1234567890987654321
#define INF 1234567890
#define pb push_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN 300006
#define MAXK 26
#define MAXX 15000006
#define ll /*long long*/ int
#define ld long double
#define rep0(kk, l1, l2)for(ll kk = l1; kk < l2; kk++)
#define rep1(kk, l1, l2)for(ll kk = l1; kk <= l2; kk++)
#define foritr(itr, A) for(set<ll>::iterator itr = A.begin(); itr != A.end(); itr++)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ii++)
#define cr(x) cerr << #x << " = " << x << "\n";
#define crA(x, A) cerr << #x << " = " << A[x] << "\n";
#define spacing if(db)cout << " ";
#define space " "
#define cbr cout << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)));
#define bg(ms) (*ms.begin())
#define ed(ms) (*prev(ms.end(), 1))
#define addedge(a, b, c, v) v[(a)].pb(pi((b), (c))); v[(b)].pb(pi((a), (c)))
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n, c, A[MAXN/3], B[MAXN/3], q, C;
const long long MOD = (ll)10007;
struct node{
  int s,e,m; short c;
	//ll s, e, m, v, dpdp[25-23],c,I;
  int dp[25];
	node *l, *r;
	node(ll _s, ll _e)
	{
		s = _s, e = _e, m = (s+e)/2; c = min(e-s+1,C);
		//v = 0; I = 0;
		mmst(dp,0);
		if(s!=e)
		{
			l = new node(s,m);
			r = new node(m+1,e);
		}
		if(s==e)
		{
			dp[0] = (B[s])%MOD;
			dp[1] = A[s]%MOD;
			return;
		}
		FOR(i,0,c)
		{
			dp[i] = 0;
			for(ll j = 0; j <= i; j++)
			{
				dp[i] += ((l->dp[j]%MOD * r->dp[i-j]%MOD)%MOD);
				dp[i]%=MOD;
			}
		}
		for(ll i = 0; i <= c; i++)
		{
			for(ll j = c-i; j <= c; j++)
			{
				dp[c] += ((l->dp[i]%MOD * r->dp[j]%MOD)%MOD);
				dp[c] %= MOD;
			}
		}
		return;
	}
	void update(ll x)
	{
		if(s==e)
		{
			dp[0] = (B[s])%MOD;
			dp[1] = A[s]%MOD;
			return;
		}
		if(x>m) r->update(x);
		else l->update(x);
		mmst(dp,0);
		FOR(i,0,c)
		{
			dp[i] = 0;
			for(ll j = 0; j <= i; j++)
			{
				dp[i] += ((l->dp[j]%MOD * r->dp[i-j]%MOD)%MOD);
				dp[i]%=MOD;
			}
		}
		for(ll i = 0; i <= c; i++)
		{
			for(ll j = c-i; j <= c; j++)
			{
				dp[c] += ((l->dp[i]%MOD * r->dp[j]%MOD)%MOD);
				dp[c] %= MOD;
			}
		}
		//assert(l->dp[c+1] == 0);
		//assert(r->dp[c+1] == 0);
		// FOR(i,0,c+1)
		// {
			// FOR(j,0,c+1) if(i+j > c) I += ((l->dp[i] * r->dp[j])%MOD);
		// }
		return;
	}
	ll sz()
	{
		return e-s+1;
	}
	void trace()
	{
		if(s==e) { cout << s << ": " << dp[0] << ' ' << dp[1] << '\n'; return; }
		l->trace();
		r->trace();
		cout << s << ' ' << m << ' ' << e << ' ' << dp[0]  << ' ' << dp[1] << ' ' << dp[2] << ' ' << dp[3] << '\n';
	}
} *seg;
int main()
{
	FAST
	cin >> n >> c; C=c;
	FOR(i,0,n) cin >> A[i];
	FOR(i,0,n) cin >> B[i];
	seg = new node(0, n-1);
	cin >> q;
	FOR(ii,0,q)
	{
		ll x, a, b;
		cin >> x >> a >> b; --x;
		A[x]=a,B[x]=b;
		seg->update(x);
		cout << seg->dp[c] << "\n";
		// seg->trace();
	}
}
/*
4 2
1 2 3 4
1 2 3 4
1
4 1 1
* */

• Subtask 1: 140 / 140