Submission #1272741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272741		jjajajajja	Relativnost (COCI15_relativnost)	C++20	56 / 140	745 ms	47916 KiB

relativnost

/*
 |---------------------------------------------|
 |       Author  : Le Hoang An                 |
 |     From  :  Bien Hoa Gifted High School    |
 |---------------------------------------------|
 |                ADOMINATION                  |
 |---------------------------------------------|
*/
#pragma GCC optimize("02,unroll-loops")
#include <bits/stdc++.h>
#define f0(i, n) for(int i=0; i<n; i++)
#define f1(i, n) for(int i=1; i<=n; i++)
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define el cout << "\n";
#define sz(A) (int)A.size()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOD(i, r, l) for (int i = r; i >= l; i--)
#define all(x) x.begin(), x.end()
#define Albaz                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                     \
    cout.tie(NULL);
#define Ado signed main()
using namespace std;
//#define int long long
#define itn int
typedef long long ll;
typedef pair<int, int> ii;
typedef unsigned long long ull;
typedef string str;
typedef vector<int> vi;
const int maxn = 100002;
const int mod = 1e4 + 7;
const ll inf = 1e18;
#define bit(mask, i) ((mask>>i)&1)
#define lon(x) ((1ll) << (x))
template <class X, class Y>
    bool maximize(X &x, const Y&y)
    {
        if(x<y)
        {
            x=y;
            return true;
        }
        else return false;
    }
template <class X, class Y>
    bool minimize(X &x, const Y&y)
    {
        if(x>y)
        {
            x=y;
            return true;
        }
        else return false;
    }

void file()
{
      #define TASK "relativnost"
    if(fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
}
void addmod(ll &x, ll y){
    x += y;
    if(x >= mod) x -= mod;
}
void submod(ll &x, ll y){
    x -= y;
    if(x < 0) x += mod;
}
void mulmod(ll &x, ll y){
    x = (x * y) % mod;
}
int n, k, q, g[maxn], c[maxn];

namespace sub1{
    ll sub = 0, total = 0;
    vector<vector<ll>> dp;
    void solve(){
       while(q--){
            int pos, ng, nc; cin >> pos >> ng >> nc;
            g[pos] = ng; c[pos] = nc;
            dp.assign(n + 1, vector<ll>(k + 1, 0));
            sub = 0; total = 1;
            FOR(i, 1, n) total = (total * (c[i] + g[i])) % mod;
            dp[0][0] = 1;
            FOR(i, 1, n){
                FOR(j, 0, k - 1){
                    dp[i][j] = dp[i - 1][j] * c[i] % mod;
                    if(j > 0) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * g[i] % mod) % mod;
                }
            }
            FOR(j, 0, k - 1) addmod(sub, dp[n][j]);
            cout << (total - sub + 1ll * mod * mod) % mod << " ";
       }
    }
}
namespace sub2{
    const int kmax = 21;
    static ll poly[4 * maxn][kmax];
    static ll prodv[4 * maxn];
    struct Query{
        int pos, ng, nc;
        Query(int _pos = 0, int _ng = 0, int _nc = 0){
            pos = _pos; ng = _ng; nc = _nc;
        }
    };
    vector<Query> que;
    struct SegTree{
        void Merge(int node, int L, int R){
            int tmp[kmax];
            FOR(i, 0, k - 1) tmp[i] = 0;
            FOR(i, 0, k - 1){
                int Ai = poly[L][i];
                if(Ai == 0) continue;
                FOR(j, 0, k - 1){
                    int ij = i + j;
                    if(i + j >= k) continue;
                    int Bj = poly[R][j];
                    tmp[ij] = (tmp[ij] + 1ll * Ai * Bj % mod) % mod;
                }
            }
            FOR(t, 0, k - 1) poly[node][t] = tmp[t];
            prodv[node] = (prodv[L] * prodv[R]) % mod;
        }
        void build(int node, int l, int r){
            if(l == r){
                FOR(t, 0, k - 1) poly[node][t] = 0;
                poly[node][0] = c[l];
                if(k > 1) poly[node][1] = g[l];
                prodv[node] = (c[l] + g[l]) % mod;
                return;
            }
            int mid = (l + r) >> 1;
            build(node * 2, l, mid);
            build(node * 2 + 1, mid + 1, r);
            Merge(node, node * 2, node * 2 + 1);
        }
        void update(int node, int l, int r, int pos){
            if(l == r){
                FOR(t, 0, k - 1) poly[node][t] = 0;
                poly[node][0] = c[l];
                if(k > 1) poly[node][1] = g[l];
                prodv[node] = (c[l] + g[l]) % mod;
                return;
            }
            int mid = (l + r) >> 1;
            if(pos <= mid) update(node * 2, l, mid, pos);
            else update(node * 2 + 1, mid + 1, r, pos);
            Merge(node, node * 2, node * 2 + 1);
        }
    } tree;
    void solve(){
        FOR(i, 1, q){
            int pos, ng, nc; cin >> pos >> ng >> nc;
            que.ep(pos, ng, nc);
        }
        tree.build(1, 1, n);
        for(const auto &[pos, ng, nc] : que){
            g[pos] = ng; c[pos] = nc;
            tree.update(1, 1, n, pos);
            ll total = prodv[1];
            ll sub = 0;
            FOR(t, 0, k - 1) addmod(sub, poly[1][t]);
            cout << (total - sub + 1ll * mod * mod) % mod << " ";
        }
    }
}
Ado
{
    Albaz;
    file();
    cin >> n >> k;
    FOR(i, 1, n) cin >> g[i];
    FOR(i, 1, n) cin >> c[i];
    cin >> q;
    if(n <= 1000 && q <= 1000) return sub1::solve(), 0;
    return sub2::solve(), 0;
    return 0;
}

Compilation message (stderr)

relativnost.cpp: In function 'void file()':
relativnost.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
relativnost.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 56 / 140