# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
98671 | long10024070 | Relativnost (COCI15_relativnost) | C++11 | 3941 ms | 25232 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define Link ""
#include <iostream>
#include <cstdio>
#include <array>
#define TASK "RELATIVNOST"
using namespace std;
const int Mod = 1e4 + 7;
const int maxn = 1e5 + 10;
const int maxc = 21;
array <int,maxc> None;
int n,c,a[maxn],b[maxn],q;
struct T_node
{
int l,r;
array <int,maxc> val;
} node[maxn*6];
void Enter()
{
cin >> n >> c;
for (int i=1;i<=n;++i) {
cin >> a[i];
a[i] %= Mod;
}
for (int i=1;i<=n;++i) {
cin >> b[i];
b[i] %= Mod;
}
}
void Init()
{
fill(None.begin(),None.end(),0);
None[0] = 1;
}
array <int,maxc> operator + (array <int,maxc> a, array <int,maxc> b)
{
array <int,maxc> res;
fill(res.begin(),res.end(),0);
long long s = 0;
for (int i=0;i<=c;++i)
for (int j=0;j<=c;++j)
if (i + j < c)
res[i+j] += a[i] * b[j];
else
s += a[i] * b[j];
for (int i=0;i<c;++i)
res[i] %= Mod;
res[c] = s % Mod;
return res;
}
void Build_tree(int i, int l, int r)
{
node[i].l = l;
node[i].r = r;
if (l != r) {
Build_tree(i*2,l,(l+r)/2);
Build_tree(i*2+1,(l+r)/2+1,r);
node[i].val = node[i*2].val + node[i*2+1].val;
}
else {
node[i].val[0] = b[l];
node[i].val[1] = a[l];
}
}
void Update(int i, int id)
{
if (node[i].r < id || id < node[i].l)
return;
if (node[i].l == node[i].r) {
node[i].val[0] = b[id];
node[i].val[1] = a[id];
}
else {
Update(i*2,id);
Update(i*2+1,id);
node[i].val = node[i*2].val + node[i*2+1].val;
}
}
array <int,maxc> Query(int i, int l, int r)
{
if (node[i].r < l || r < node[i].l)
return None;
if (l <= node[i].l && node[i].r <= r)
return node[i].val;
else
return Query(i*2,l,r) + Query(i*2+1,l,r);
}
void Solve()
{
Build_tree(1,1,n);
for (cin>>q;q>0;--q) {
int p,_a,_b;
cin >> p >> _a >> _b;
a[p] = _a % Mod;
b[p] = _b % Mod;
Update(1,p);
array <int,maxc> Left = Query(1,1,p-1);
array <int,maxc> Mid = Query(1,p,p);
array <int,maxc> Right = Query(1,p+1,n);
array <int,maxc> res = Left + Mid + Right;
cout << res[c] << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifdef LHL
freopen(".INP","r",stdin);
freopen(".OUT","w",stdout);
#else
// freopen(TASK".INP","r",stdin);
// freopen(TASK".OUT","w",stdout);
#endif // LHL
Enter();
Init();
Solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |