Submission #98666

#	Time	Username	Problem	Language	Result	Execution time	Memory
98666		leduykhongngu	Relativnost (COCI15_relativnost)	C++14	140 / 140	2094 ms	23248 KiB

relativnost

#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=(_b); ++i)
#define FORR(i,a,b) for (int i=(a),_b=(b); i>=(_b); --i)
#define REP(i,b) for (int i=0,_b=(b); i<(_b); ++i)
#define endl '\n'
#define sz(x) (int) x.size()
#define mod %
#define fillchar(x,y,z) memset(x,z,y)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define sqr(x) ((x)*(x))
typedef long long int64;
typedef unsigned long long qword;
using namespace std;
const int base=10007;
const int maxn=1e5+5;
int st[maxn*4][21];
int a[maxn],b[maxn];
int n,C;
inline void Merge(int L[], int R[], int a[])
{
}
void build(int id, int l, int r)
{
    if (l==r) {
        st[id][0]=b[l];
        st[id][1]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid); build(id<<1|1,mid+1,r);
    FOR(x,0,C) st[id][x]=0;
    FOR(x,0,C) FOR(y,0,C) {
        st[id][min(x+y,C)]+=st[id<<1][x]*st[id<<1|1][y];
        if (st[id][min(x+y,C)]>2e9) st[id][min(x+y,C)]%=base;
    }
    FOR(x,0,C) if (st[id][x]>=base) st[id][x]%=base;
}
void update(int id, int l, int r, int u, int x, int y)
{
    if (l>u||r<u) return;
    if (l==r) {
        st[id][0]=y;
        st[id][1]=x;
        return;
    }
    int mid=(l+r)>>1;
    update(id<<1,l,mid,u,x,y); update(id<<1|1,mid+1,r,u,x,y);
    FOR(x,0,C) st[id][x]=0;
    FOR(x,0,C) FOR(y,0,C) {
        st[id][min(x+y,C)]+=st[id<<1][x]*st[id<<1|1][y];
        if (st[id][min(x+y,C)]>2e9) st[id][min(x+y,C)]%=base;
    }
    FOR(x,0,C) if (st[id][x]>=base) st[id][x]%=base;
}
int main()
{
    #ifdef meomeomeooooo
        freopen("input.txt","r",stdin);
        //freopen(".out","w",stdout);
    #endif // meomeomeooooo
    iostream::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> C;
    FOR(i,1,n) cin >> a[i];
    FOR(i,1,n) cin >> b[i];
    FOR(i,1,n) a[i]%=base,b[i]%=base;
    build(1,1,n);
    int q;
    cin >> q;
    FOR(i,1,q) {
        int id,x,y;
        cin >> id >> x >> y;
        x%=base; y%=base;
        update(1,1,n,id,x,y);
        cout << st[1][C] << endl;
    }
    return 0;
}

• Subtask 1: 140 / 140