oj.uz

답안 #1005735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1005735 2024-06-23T00:38:48 Z vjudge1 Relativnost (COCI15_relativnost) C++17
140 / 140
 2866 ms 17832 KB 
#include <bits/stdc++.h>
using namespace std;


const int MAXN=100005;
int n,c;
int a[MAXN], b[MAXN];
int T[2*MAXN][21]; 
const int mod = 10007;

void update(int x){
  for (int i=0; i<=c; i++) T[x][i]=0;
  for (int i=0; i<=c; i++){
    for (int j=0; j<=c; j++){
       (T[x][min(c,i+j)]+=(T[2*x][i]*T[2*x+1][j])%mod)%=mod;
    }
  }
}

void change(int x){
  x+=n;
  memset(T[x], 0, sizeof T[x]);
  T[x][0]=b[x-n]%mod, T[x][1]=a[x-n]%mod;

  for (x/=2; x>0; x/=2) {
    update(x);
  }
}


signed main(){
  cin>>n>>c;
  for (int i=0; i<n; i++) cin>>a[i];
  for (int i=0; i<n; i++) cin>>b[i];
  for (int i=0; i<n; i++){
    T[i+n][0]=b[i]%mod;
    T[i+n][1]=a[i]%mod;
  }
  for (int i=n-1; i>=1; i--){
    update(i);
  }

  int q; cin>>q;
  while(q--){
    int p; cin>>p;
    p--;
    cin>>a[p]>>b[p];
    change(p);
    cout<<T[1][c]<<'\n';
  }




}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2652 KB Output is correct
2 Correct 13 ms 2396 KB Output is correct
3 Correct 23 ms 2624 KB Output is correct
4 Correct 431 ms 13392 KB Output is correct
5 Correct 1243 ms 17748 KB Output is correct
6 Correct 1880 ms 17832 KB Output is correct
7 Correct 810 ms 13392 KB Output is correct
8 Correct 454 ms 17492 KB Output is correct
9 Correct 799 ms 15696 KB Output is correct
10 Correct 2866 ms 15768 KB Output is correct