oj.uz

Submission #93623

# Submission time Handle Problem Language Result Execution time Memory
93623 2019-01-10T11:42:47 Z Milki Relativnost (COCI15_relativnost) C++14
140 / 140
 2502 ms 24752 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int mod = 1e4 + 7, MAXN = 1e5 + 5, MAXC = 22, off = 1 << 17;

int n, c, q;
ll a[MAXN], b[MAXN];

int add(int x, int y){
  x += y;
  if(x >= mod) return x - mod;
  return x;
}

int mul(ll x, ll y){
  return x * y % mod;
}

struct Tournament{
  int t[2 * off][MAXC];
  Tournament(){ memset(t, 0, sizeof(t)); REP(i, 2 * off) t[i][0] = 1;}

  void merge(int x, int y, int z){
    REP(i, c + 1)
      t[z][i] = 0;

    REP(i, c){
      REP(j, i + 1)
        t[z][i] = add(t[z][i], mul(t[x][j], t[y][i - j]) );
    }
    REP(i, c + 1)
      REP(j, c + 1)
        if(i + j >= c)
          t[z][c] = add(t[z][c], mul(t[x][i], t[y][j]));
  }
  void build(){
    for(int x = off - 1; x > 0; --x)
      merge(x * 2, x * 2 + 1, x);
  }
  void ubaci(int x){
    t[x + off][0] = b[x] % mod;
    t[x + off][1] = a[x] % mod;
  }
  void update(int x){
    t[x + off][0] = b[x] % mod;
    t[x + off][1] = a[x] % mod;
    x += off; x >>= 1;
    for( ; x > 0; x >>= 1)
      merge(x * 2, x * 2 + 1, x);
  }
} T;

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n >> c;
  REP(i, n) cin >> a[i];
  REP(i, n) cin >> b[i];
  REP(i, n) T.ubaci(i);
  T.build();
  cin >> q;
  REP(i, q){
    int A, B, C; cin >> A >> B >> C; A --;
    a[A] = B; b[A] = C;
    T.update(A);
    cout << T.t[1][c] << "\n";
  }
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 22904 KB Output is correct
2 Correct 97 ms 22904 KB Output is correct
3 Correct 213 ms 22904 KB Output is correct
4 Correct 358 ms 24000 KB Output is correct
5 Correct 1041 ms 24752 KB Output is correct
6 Correct 1533 ms 24752 KB Output is correct
7 Correct 714 ms 24236 KB Output is correct
8 Correct 352 ms 24528 KB Output is correct
9 Correct 653 ms 24568 KB Output is correct
10 Correct 2502 ms 24752 KB Output is correct