# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
371252 | Atill83 | Relativnost (COCI15_relativnost) | C++14 | 4099 ms | 1604 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e4+7;
const int MAXN = (int) 1e5+5;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, c;
int a[MAXN], b[MAXN];
const int BS = 700;
int dp[MAXN][21];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
#ifdef Local
freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
#endif
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 * BS < n; i++){
dp[i][0] = 1;
for(int j = i*BS; j < min((i + 1) * BS, n); j++){
a[j] %= mod;
b[j] %= mod;
int a_cur = a[j], b_cur = b[j];
dp[i][c] = (dp[i][c - 1] * a_cur % mod + dp[i][c] * (a_cur + b_cur) % mod) % mod;
for(int l = c - 1; l > 0; l--){
dp[i][l] = (dp[i][l - 1] * a_cur % mod + dp[i][l] * b_cur % mod) % mod;
}
dp[i][0] = dp[i][0] * b_cur % mod;
}
}
int q;
cin>>q;
for(int i = 0; i < q; i++){
int idx;
cin>>idx;
idx--;
cin>>a[idx]>>b[idx];
a[idx] %= mod;
b[idx] %= mod;
int block = idx / BS;
for(int j = 0; j <= c; j++)
dp[block][j] = 0;
dp[block][0] = 1;
for(int j = block*BS; j < min((block + 1) * BS, n); j++){
int a_cur = a[j], b_cur = b[j];
dp[block][c] = (dp[block][c - 1] * a_cur % mod + dp[block][c] * (a_cur + b_cur) % mod) % mod;
for(int l = c - 1; l > 0; l--){
dp[block][l] = (dp[block][l - 1] * a_cur % mod + dp[block][l] * b_cur % mod) % mod;
}
dp[block][0] = dp[block][0] * b_cur % mod;
}
vector<int> ans(c + 1, 0);
ans[0] = 1;
for(int i = 0; i*BS < n; i++){
vector<int> nans(c + 1, 0);
for(int l = c; l >= 0; l--){
for(int j = c; j >= 0; j--){
nans[(min(c, l + j))] += ans[l] * dp[i][j] % mod;
nans[(min(c, l + j))] %= mod;
}
}
ans = nans;
}
cout<<ans[c]<<endl;
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |