oj.uz

답안 #465405

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
465405 2021-08-15T21:44:59 Z JovanB Relativnost (COCI15_relativnost) C++17
140 / 140
 130 ms 5120 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int MOD = 10007;

int add(int a, int b){ a += b; if(a >= MOD) a -= MOD; return a; }
int sub(int a, int b){ return add(a, MOD - b); }
int mul(int a, int b){ return (1LL*a*b)%MOD; }
int pw(int a, int b){
    if(b == 0) return 1;
    int res = pw(a, b/2);
    res = mul(res, res);
    if(b%2) res = mul(res, a);
    return res;
}
int inv(int a){ return pw(a, MOD - 2); }

const int N = 100000;

int dp[25];
int a[N+5], b[N+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
	cout.precision(10);
	cout << fixed;

    int n, c;
    cin >> n >> c;
    c--;
    int svi = 1;
    int van = 1;
    for(int i=1; i<=n; i++) cin >> b[i];
    for(int i=1; i<=n; i++) cin >> a[i];
    set <int> zeroes;
    int jos = 1;
    for(int i=1; i<=n; i++){
        a[i] %= MOD;
        b[i] %= MOD;
        if(a[i] == 0){
            zeroes.insert(i);
            jos = mul(jos, b[i]);
            continue;
        }
        b[i] = mul(b[i], inv(a[i]));
        van = mul(van, a[i]);
        svi = mul(svi, b[i] + 1);
    }
    dp[0] = 1;
    for(int i=1; i<=n; i++){
        if(!a[i]) continue;
        for(int j=c; j>=1; j--){
            dp[j] = add(dp[j], mul(dp[j-1], b[i]));
        }
    }
    int qrs;
    cin >> qrs;
    while(qrs--){
        int ind, _a, _b;
        cin >> ind >> _b >> _a;
        _a %= MOD;
        _b %= MOD;
        if(a[ind]){
            van = mul(van, inv(a[ind]));
            svi = mul(svi, inv(b[ind] + 1));
            for(int j=1; j<=c; j++) dp[j] = sub(dp[j], mul(dp[j-1], b[ind]));
        }
        else zeroes.erase(ind), jos = mul(jos, inv(b[ind]));
        a[ind] = _a;
        b[ind] = _b;
        if(a[ind]){
            _b = mul(_b, inv(_a));
            b[ind] = _b;
            van = mul(van, a[ind]);
            svi = mul(svi, b[ind] + 1);
            for(int j=c; j>=1; j--) dp[j] = add(dp[j], mul(dp[j-1], b[ind]));
        }
        else zeroes.insert(ind), jos = mul(jos, b[ind]);
        int res = svi;
        for(int j=0; j<=c - int(zeroes.size()); j++) res = sub(res, dp[j]);
        if(zeroes.size() > c) cout << "0\n";
        else cout << mul(res, mul(van, jos)) << "\n";
    }
	return 0;
}

Compilation message

relativnost.cpp: In function 'int main()':
relativnost.cpp:84:26: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |         if(zeroes.size() > c) cout << "0\n";
      |            ~~~~~~~~~~~~~~^~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 78 ms 3696 KB Output is correct
5 Correct 114 ms 5072 KB Output is correct
6 Correct 106 ms 4676 KB Output is correct
7 Correct 88 ms 3896 KB Output is correct
8 Correct 80 ms 4220 KB Output is correct
9 Correct 116 ms 5120 KB Output is correct
10 Correct 130 ms 4956 KB Output is correct