oj.uz

Submission #98666

# Submission time Handle Problem Language Result Execution time Memory
98666 2019-02-25T03:16:09 Z leduykhongngu Relativnost (COCI15_relativnost) C++14
140 / 140
 2094 ms 23248 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct
2 Correct 9 ms 512 KB Output is correct
3 Correct 17 ms 512 KB Output is correct
4 Correct 365 ms 12028 KB Output is correct
5 Correct 1043 ms 23164 KB Output is correct
6 Correct 1452 ms 23248 KB Output is correct
7 Correct 778 ms 11976 KB Output is correct
8 Correct 426 ms 22908 KB Output is correct
9 Correct 782 ms 23104 KB Output is correct
10 Correct 2094 ms 23032 KB Output is correct