Submission #527109

#	Time	Username	Problem	Language	Result	Execution time	Memory
527109		colazcy	Relativnost (COCI15_relativnost)	C++11	140 / 140	461 ms	13764 KiB

relativnost

#include <cstdio>
#include <map>
#include <utility>
#include <cassert>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_LIM = lim,REPN = 1;REPN <= REPN_LIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("Line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
constexpr int maxn = 1e5 + 10,maxm = 20,mod = 1e4 + 7;
int qpow(int base,int b){
	int res = 1;
	while(b){
		if(b & 1)res = res * base % mod;
		base = base * base % mod;
		b >>= 1;
	}
	return res;
}
int n,c,a[maxn],b[maxn];
namespace seg{
	#define ls (x << 1)
	#define rs (x << 1 | 1)
	unsigned short val[maxn << 2][maxm];
	void pushup(const int x){
		rep(i,0,c - 1){
			int s = 0;
			rep(j,0,i)s += int(val[ls][j]) * val[rs][i - j];
			val[x][i] = s % mod;
		}
	}
	void build(const int l = 1,const int r = n,const int x = 1){
		if(l == r){
			let a = ::a[l],b = ::b[l];
			val[x][0] = b % mod;
			val[x][1] = a % mod;
			return;
		}
		let mid = (l + r) >> 1;
		build(l,mid,ls);
		build(mid + 1,r,rs);
		pushup(x);
	}
	void modify(const int p,const int a,const int b,const int l = 1,const int r = n,const int x = 1){
		if(l == r){
			val[x][0] = b % mod;
			val[x][1] = a % mod;
			return;
		}
		let mid = (l + r) >> 1;
		if(p <= mid)modify(p,a,b,l,mid,ls);
		else modify(p,a,b,mid + 1,r,rs);
		pushup(x);
	}
	#undef ls
	#undef rs
}
int ans = 1;
int main(){
	// std::freopen("relativnost.in","r",stdin);
	// std::freopen("relativnost.out","w",stdout);
	std::scanf("%d %d",&n,&c);
	rep(i,1,n)std::scanf("%d",a + i);
	rep(i,1,n)std::scanf("%d",b + i);
	rep(i,1,n)
		a[i] %= mod,
		b[i] %= mod,
		ans = ans * ((a[i] + b[i]) % mod) % mod;
	seg::build();
	int q; std::scanf("%d",&q);
	repn(q){
		int p,x,y; std::scanf("%d %d %d",&p,&x,&y);
		seg::modify(p,x,y);
		ans = ans * qpow((a[p] + b[p]) % mod,mod - 2) % mod;
		x %= mod,y %= mod;
		ans = ans * ((x + y) % mod) % mod;
		a[p] = x; b[p] = y;

		int out = ans;
		rep(i,0,c - 1)
			out -= seg::val[1][i];
		out %= mod;
		out += mod;
		out %= mod;
		std::printf("%d\n",out);
	}
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}

Compilation message (stderr)

relativnost.cpp: In function 'int main()':
relativnost.cpp:64:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |  std::scanf("%d %d",&n,&c);
      |  ~~~~~~~~~~^~~~~~~~~~~~~~~
relativnost.cpp:65:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  rep(i,1,n)std::scanf("%d",a + i);
      |            ~~~~~~~~~~^~~~~~~~~~~~
relativnost.cpp:66:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  rep(i,1,n)std::scanf("%d",b + i);
      |            ~~~~~~~~~~^~~~~~~~~~~~
relativnost.cpp:72:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  int q; std::scanf("%d",&q);
      |         ~~~~~~~~~~^~~~~~~~~
relativnost.cpp:74:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   int p,x,y; std::scanf("%d %d %d",&p,&x,&y);
      |              ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140