#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
using ll=long long;
using ld=long double;
template <typename T> inline void read(T &x){
char c;
bool nega=0;
while((!isdigit(c=getchar()))&&(c!='-'));
if(c=='-'){
nega=1;
c=getchar();
}
x=c-48;
while(isdigit(c=getchar())) x=x*10+c-48;
if(nega) x=-x;
}
template <typename T> inline void writep(T x){
if(x>9) writep(x/10);
putchar(x%10+48);
}
template <typename T> inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
writep(x);
}
template <typename T> inline void writeln(T x){
write(x);
putchar('\n');
}
#define taskname "RELATIVNOST"
///https://oj.uz/problem/view/COCI15_relativnost
int n, k;
const int base=10007;
class segment_tree{
public:
using pointer=segment_tree*;
pointer left, right;
int f[20];
int all;
int l, r, m;
segment_tree(int l, int r){
this->l=l;
this->r=r;
m=(l+r)/2;
FFOR(i, 0, k) f[i]=0;
if(l!=r){
left=new segment_tree(l, m);
right=new segment_tree(m+1, r);
}
}
void update(int u, int a, int b){
if(l==r){
f[1]=a%base;
f[0]=b%base;
all=(a+b)%base;
}
else{
if(m>=u) left->update(u, a, b);
else right->update(u, a, b);
all=(left->all*right->all)%base;
FFOR(i, 0, k) f[i]=0;
FFOR(i, 0, k) if(left->f[i]) FFOR(j, 0, k-i) if(right->f[j]) f[i+j]+=left->f[i]*right->f[j];
FFOR(i, 0, k) f[i]%=base;
}
}
int get(){
int res=all;
FFOR(i, 0, k) res-=f[i];
res%=base;
if(res<0) res+=base;
return res;
}
};
segment_tree::pointer tree;
int a[100001];
int b[100001];
int main(){
#ifdef Uiharu
if(fopen(taskname".in", "r"))
freopen(taskname".in", "r", stdin);
#endif // Uiharu
read(n);
read(k);
FOR(i, 1, n) read(a[i]);
FOR(i, 1, n) read(b[i]);
tree=new segment_tree(1, n);
FOR(i, 1, n) tree->update(i, a[i], b[i]);
{
int q, u, a, b;
read(q);
FOR(i, 1, q){
read(u);
read(a);
read(b);
tree->update(u, a, b);
writeln(tree->get());
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
640 KB |
Output is correct |
| 2 |
Correct |
0 ms |
512 KB |
Output is correct |
| 3 |
Correct |
10 ms |
512 KB |
Output is correct |
| 4 |
Correct |
269 ms |
14176 KB |
Output is correct |
| 5 |
Correct |
503 ms |
23104 KB |
Output is correct |
| 6 |
Correct |
736 ms |
24404 KB |
Output is correct |
| 7 |
Correct |
428 ms |
16924 KB |
Output is correct |
| 8 |
Correct |
294 ms |
23800 KB |
Output is correct |
| 9 |
Correct |
427 ms |
19832 KB |
Output is correct |
| 10 |
Correct |
957 ms |
19292 KB |
Output is correct |
