Submission #98665

#	Time	Username	Problem	Language	Result	Execution time	Memory
98665		IOrtroiii	Relativnost (COCI15_relativnost)	C++14	0 / 140	1275 ms	23672 KiB

relativnost

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 100005;
const int C = 20;
const int mod = 10007;

struct Info {
	int mul;
	int d[C];
	void upd(int a,int b) {
		mul = (a + b) % mod;
		d[0] = b % mod;
		d[1] = a % mod;
	}
	Info operator + (const Info &b) const {
		Info c;
		c.mul = (ll) mul * b.mul % mod;
		for (int i = 0; i < C; ++i) {
			for (int j = 0; i + j < C; ++j) {
				c.d[i + j] += (ll) (d[i] * b.d[j]) % mod;
				if (c.d[i + j] >= mod) {
					c.d[i + j] -= mod;
				}
			}
		}
		return c;
	}
};

int a[N], b[N];
Info t[N << 2];

void build(int v,int l,int r) {
	if (l == r) {
		t[v].upd(a[l], b[l]);
		return;
	}
	int md = (l + r) >> 1;
	build(v << 1, l, md);
	build(v << 1 | 1, md + 1, r);
	t[v] = t[v << 1] + t[v << 1 | 1];
}

void upd(int v,int l,int r,int p,int a,int b) {
	if (l == r) {
		t[v].upd(a, b);
		return;
	}
	int md = (l + r) >> 1;
	if (p <= md) {
		upd(v << 1, l, md, p, a, b);
	} else {
		upd(v << 1 | 1, md + 1, r, p, a, b);
	}
	t[v] = t[v << 1] + t[v << 1 | 1];
} 

int main() {
	
	int n, c;
	
	scanf("%d %d", &n, &c);
	
	for (int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
	} 
	
	for (int i = 1; i <= n; ++i) {
		scanf("%d", b + i);
	}
	
	int q;
	
	build(1, 1, n);
	scanf("%d", &q);
	while (q--) {
		int p, ap, bp;
		
		scanf("%d %d %d", &p, &ap, &bp);
		
		upd(1, 1, n, p, ap, bp);
		
		int ans = t[1].mul;
		
		for (int i = 0; i < c; ++i) {
			ans -= t[1].d[i];
			if (ans < 0) {
				ans += mod;
			}
		}
		
		printf("%d\n", ans);
	}
}

Compilation message (stderr)

relativnost.cpp: In function 'int main()':
relativnost.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &c);
  ~~~~~^~~~~~~~~~~~~~~~~
relativnost.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~
relativnost.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", b + i);
   ~~~~~^~~~~~~~~~~~~
relativnost.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
relativnost.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &p, &ap, &bp);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 140