oj.uz

답안 #98694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98694 2019-02-25T04:16:57 Z Mercenary Relativnost (COCI15_relativnost) C++11
140 / 140
 1393 ms 25144 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];
        a[i] %= mod;
    }
    for(int i = 1 ; i <= n ; ++i){
        cin >> b[i];
        b[i] %= mod;
    }
    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) {
    fill_n(res.dp.begin(),c,0);
    for(int i = 0 ; i < c ; ++i){
        for(int j = 0 ; j < c - i ; ++j){
            add(res.dp[i + j],x.dp[i] * other.dp[j] % mod);
        }
    }
}

void build(int x , int l , int r){
    s[x].dp.resize(c);
    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);
    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 inv[mod];

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);
    int res = 1;
    for(int i = 1 ; i < mod ; ++i)inv[i] = Pow(i,mod-2);
    for(int i = 1 ; i <= n ; ++i)res = (ll)res * (a[i] + b[i]) % mod;
    while(q--){
        cin >> p;
        res = res * inv[(a[p] + b[p]) % mod] % mod;
        cin >> a[p] >> b[p];
        a[p] %= mod;b[p] %= mod;
        res = 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];
            if(tmpres < 0)tmpres += mod;
        }
        cout << tmpres << '\n';
    }
}

Compilation message

relativnost.cpp: In function 'void build(int, int, int)':
relativnost.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
relativnost.cpp: In function 'void update(int, int, int)':
relativnost.cpp:77:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
relativnost.cpp: In function 'int main()':
relativnost.cpp:89:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP", "r",stdin) ,
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
         freopen(taskname".OUT", "w",stdout);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
relativnost.cpp:89:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 9856 KB Output is correct
2 Correct 16 ms 9856 KB Output is correct
3 Correct 20 ms 9984 KB Output is correct
4 Correct 296 ms 15452 KB Output is correct
5 Correct 959 ms 21700 KB Output is correct
6 Correct 972 ms 25144 KB Output is correct
7 Correct 467 ms 18552 KB Output is correct
8 Correct 333 ms 19216 KB Output is correct
9 Correct 530 ms 17912 KB Output is correct
10 Correct 1393 ms 24184 KB Output is correct