| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 98687 | 2019-02-25T04:02:09 Z | Mercenary | Relativnost (COCI15_relativnost) | C++14 | 63 ms | 20984 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 q , p;
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;
}
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{
vector<int>dp;
node(){};
}s[maxn * 4];
//20 * maxn * 4 = 8e6
void Merge(node & res , const node & x , const node & other) {
res.dp.resize(min((int)x.dp.size()+(int)other.dp.size(),c),0);
for(int i = 0 ; i < res.dp.size() ; ++i)res.dp[i] = 0;
for(int i = 0 ; i < c ; ++i){
for(int j = 0 ; j < c - i ; ++j){
add(res.dp[i + j],(ll)x.dp[i] * other.dp[j] % mod);
}
}
}
void build(int x , int l , int r){
if(l == r){
s[x].dp.resize(2,0);
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);
Merge(s[x], s[x * 2],s[x * 2 + 1]);
}
void update(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;
if(mid >= p)update(x * 2 , l , mid);
else update(x * 2 + 1 , mid + 1 , r);
Merge(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--){
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);
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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 28 ms | 19448 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Runtime error | 28 ms | 19448 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Runtime error | 35 ms | 19576 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Runtime error | 46 ms | 20088 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 | Runtime error | 42 ms | 20860 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 | Runtime error | 49 ms | 20984 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 | Runtime error | 52 ms | 20472 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 | Runtime error | 63 ms | 20956 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 | Runtime error | 45 ms | 20728 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 | Runtime error | 43 ms | 20600 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |