| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 98678 | 2019-02-25T03:43:20 Z | Mercenary | Relativnost (COCI15_relativnost) | C++11 | 1141 ms | 33044 KB |
#include<bits/stdc++.h>
using namespace std;
#define taskname "TEST"
#define pb push_back
typedef long double ld;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e4 + 7;
int n , c , a[maxn] , b[maxn];
int res = 0;
int dp[maxn][20] , q;
void enter()
{
cin >> n >> c;
for(int i = 1 ; i <= n ; ++i)cin >> a[i];
for(int i = 1 ; i <= n ; ++i)cin >> b[i];
cin >> q;
}
void brute()
{
while(q--){
int p;cin >> p;
cin >> a[p] >> b[p];
dp[0][0] = 1;
int res = 1;
for(int i = 1 ; i <= n ; ++i){
for(int j = 0 ; j < c ; ++j){
dp[i][j] = (ll)dp[i - 1][j] * b[i] % mod;
if(j)dp[i][j] = ((ll)dp[i - 1][j - 1] * a[i] + dp[i][j]) % mod;
}
res = (ll)res * (a[i] + b[i]) % mod;
}
for(int j = 0 ; j < c ; ++j){
res -= dp[n][j];
if(res < 0)res += mod;
}
cout << res << '\n';
}
}
int Pow(int a , int b){
if(b == 0)return 1;
int r = Pow(a , b / 2);
if(b & 1)return (ll)r * r % mod * a % mod;
return (ll)r * r % mod;
}
void add(int & x , int y){
x += y;
if(x < 0)x += mod;
if(x >= mod)x -= mod;
}
struct node{
int dp[20];
node(){fill_n(dp,20,0);};
node operator + (const node & other) const & {
node res;
for(int i = 0 ; i < c ; ++i){
for(int j = 0 ; j < c - i ; ++j){
add(res.dp[i + j],(ll)dp[i] * other.dp[j] % mod);
}
}
return res;
}
}s[maxn * 4];
//20 * maxn * 4 = 8e6
void build(int x , int l , int r){
if(l == r){
s[x].dp[0] = b[l];
s[x].dp[1] = a[l];
return;
}
int mid = l + r >> 1;
build(x * 2 , l , mid);
build(x * 2 + 1 , mid + 1 , r);
s[x] = s[x * 2] + s[x * 2 + 1];
}
void update(int x , int l , int r , int p){
if(l == r){
s[x].dp[0] = b[l];
s[x].dp[1] = a[l];
return;
}
int mid = l + r >> 1;
if(mid >= p)update(x * 2 , l , mid , p);
else update(x * 2 + 1 , mid + 1 , r , p);
s[x] = s[x * 2] + s[x * 2 + 1];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r"))
freopen(taskname".INP", "r",stdin) ,
freopen(taskname".OUT", "w",stdout);
enter();
build(1,1,n);
// cout << s[1].dp[0] << endl;
int res = 1;
for(int i = 1 ; i <= n ; ++i)res = (ll)res * (a[i] + b[i]) % mod;
while(q--){
int p;cin >> p;
res = (ll)res * Pow(a[p] + b[p],mod-2) % mod;
cin >> a[p] >> b[p];
res = (ll)res * (a[p] + b[p]) % mod;
update(1,1,n,p);
int tmpres = res;
for(int j = 0 ; j < c ; ++j){
tmpres -= s[1].dp[j];
// cout << s[1].dp[j] << " ";
if(tmpres < 0)tmpres += mod;
}
cout << tmpres << '\n';
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 34 ms | 31608 KB | Output is correct |
| 2 | Correct | 42 ms | 31608 KB | Output is correct |
| 3 | Correct | 44 ms | 31736 KB | Output is correct |
| 4 | Correct | 273 ms | 32364 KB | Output is correct |
| 5 | Runtime error | 621 ms | 33044 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 6 | Runtime error | 845 ms | 32772 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 7 | Correct | 421 ms | 32504 KB | Output is correct |
| 8 | Correct | 262 ms | 32476 KB | Output is correct |
| 9 | Correct | 446 ms | 32760 KB | Output is correct |
| 10 | Correct | 1141 ms | 32724 KB | Output is correct |