Submission #31654

#TimeUsernameProblemLanguageResultExecution timeMemory
31654long10024070Relativnost (COCI15_relativnost)C++11
0 / 140
0 ms1840 KiB
#include <iostream> #include <cstdio> using namespace std; const string TASK = "Relativnost"; const int Mod = 1e4 + 7; const int maxn = 1e6 + 1; struct T_node { int l,r,f[21]; }; int n,c,a[maxn],b[maxn],id[maxn]; T_node node[maxn*20]; void Enter() { cin >> n >> c; //scanf("%d%d",&n,&c); for (int i=1;i<=n;++i) cin >> a[i]; //scanf("%d",&a[i]); for (int i=1;i<=n;++i) cin >> b[i]; //scanf("%d",&b[i]); } void Build_tree(int i, int l, int r) { node[i].l = l; node[i].r = r; fill(node[i].f,node[i].f+c+1,1); if (l == r) id[l] = i; else { Build_tree(i*2,l,(l+r)/2); Build_tree(i*2+1,(l+r)/2+1,r); } } void Update(int i) { if (i == 0) return; fill(node[i].f,node[i].f+c+1,0); if (node[i].l == node[i].r) { node[i].f[1] = a[node[i].l] % Mod; node[i].f[0] = b[node[i].l] % Mod; } else for (int j=0;j<=c;++j) for (int k=0;k<=c;++k) node[i].f[min(c,j+k)] = (node[i].f[min(c,j+k)] + node[i*2].f[j] * node[i*2+1].f[k]) % Mod; Update(i/2); } void Init() { Build_tree(1,1,n); for (int i=1;i<=n;++i) Update(id[i]); } void Solve() { int q,p,A,B; for (cin>>q;q>0;--q) { cin >> p >> A >> B; ////scanf("%d%d%d",&p,&A,&B); a[p] = A; b[p] = B; Update(id[p]); cout << node[1].f[c] << '\n'; ////printf("%d\n",node[1].f[c]); } } int main() { ios_base::sync_with_stdio(false); //cin.tie(NULL); //cout.tie(NULL); //freopen((TASK+".INP").c_str(),"r",stdin); //freopen((TASK+".OUT").c_str(),"w",stdout); Enter(); Init(); Solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...