Submission #465405

#	Time	Username	Problem	Language	Result	Execution time	Memory
465405		JovanB	Relativnost (COCI15_relativnost)	C++17	140 / 140	130 ms	5120 KiB

relativnost

#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 (stderr)

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 / 140