#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
inline void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
/* online submission */
#endif
ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/**************************COCI 2016-2017 R7 P4*************************/
const int MAXN = 100000, MAXK = 17;
int N, C, A[MAXN], B[MAXN], Q, Total = 1;
const int MOD = 10007;
void modd(int &x) {
x %= MOD;
x += MOD;
x %= MOD;
}
int pow(int a, int p) {
int ret = 1;
while (p) {
if (p & 1)
ret *= a;
a *= a;
modd(ret);
modd(a);
p >>= 1;
}
return ret;
}
inline int inv(int x) { // this give the modular inverse, albeit slowly
modd(x);
return pow(x, MOD - 2);
}
struct Node {
v<short> dp;
bool isId;
Node() {
isId = 1;
}
Node(int a, int b) {
dp = v<short>(max(C, 2), 0);
isId = 0;
dp[0] = (short)(b%MOD);
dp[1] = (short)(a%MOD);
}
};
template<int SZ> struct SegmentTree {
Node data[2 * SZ];
Node combine(Node &a, Node &b) {
if (a.isId) return b;
if (b.isId) return a;
Node c(0, 0);
FOR(i, 0, C) FORE(j, 0, i) {
int add = (int)a.dp[j] * (int)b.dp[i - j];
add %= MOD;
c.dp[i] += (short)add;
c.dp[i] %= MOD;
}
return c;
}
void build() {
// ! make sure you do this first
// for (int i = 0; i < n; ++i) scanf("%d", t + n + i);
for (int i = SZ - 1; i > 0; --i)
data[i] = combine(data[i << 1], data[(i << 1) | 1]);
}
void update(int p, Node val) {
data[p += SZ] = val;
for (p >>= 1; p > 0; p >>= 1)
data[p] = combine(data[p << 1], data[(p << 1) | 1]);
}
int query() {
int sum = 0;
FOR(i, 0, C) {
sum += (int)data[1].dp[i];
sum %= MOD;
}
return sum;
}
};
SegmentTree<1 << MAXK> tree;
int main() {
io();
cin >> N >> C;
FOR(i, 0, N) cin >> A[i];
FOR(i, 0, N) cin >> B[i];
FOR(i, 0, N) {
modd(A[i]);
modd(B[i]);
tree.data[i + (1 << MAXK)] = Node(A[i], B[i]);
modd(Total *= (A[i] + B[i]));
}
tree.build();
cin >> Q;
FOR(i, 0, Q) {
int p, a, b;
cin >> p >> a >> b;
p--;
modd(a);
modd(b);
tree.update(p, Node(a, b));
modd(Total *= inv(A[p] + B[p]));
modd(Total *= a + b);
A[p] = a;
B[p] = b;
cout << (Total - tree.query() + MOD) % MOD << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
8568 KB |
Output is correct |
| 2 |
Correct |
18 ms |
8836 KB |
Output is correct |
| 3 |
Correct |
25 ms |
8836 KB |
Output is correct |
| 4 |
Correct |
391 ms |
13208 KB |
Output is correct |
| 5 |
Correct |
1025 ms |
18380 KB |
Output is correct |
| 6 |
Correct |
1459 ms |
18840 KB |
Output is correct |
| 7 |
Correct |
669 ms |
18840 KB |
Output is correct |
| 8 |
Correct |
451 ms |
18840 KB |
Output is correct |
| 9 |
Correct |
718 ms |
18840 KB |
Output is correct |
| 10 |
Correct |
2261 ms |
18840 KB |
Output is correct |
