Submission #93623

#	Time	Username	Problem	Language	Result	Execution time	Memory
93623		Milki	Relativnost (COCI15_relativnost)	C++14	140 / 140	2502 ms	24752 KiB

relativnost

#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 / 140