oj.uz

Submission #98663

# Submission time Handle Problem Language Result Execution time Memory
98663 2019-02-25T03:13:06 Z leduykhongngu Relativnost (COCI15_relativnost) C++11
140 / 140
 2844 ms 23172 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;
void Merge(int L[], int R[], int a[])
{
    FOR(x,0,C) a[x]=0;
    FOR(x,0,C) FOR(y,0,C) {
        a[min(x+y,C)]+=L[x]*R[y];
        if (a[min(x+y,C)]>2e9) a[min(x+y,C)]%=base;
    }
    FOR(x,0,C) a[x]%=base;
}
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);
    Merge(st[id<<1],st[id<<1|1],st[id]);
}
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);
    Merge(st[id<<1],st[id<<1|1],st[id]);
}
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 15 ms 512 KB Output is correct
3 Correct 16 ms 512 KB Output is correct
4 Correct 348 ms 11836 KB Output is correct
5 Correct 1089 ms 23172 KB Output is correct
6 Correct 1613 ms 23160 KB Output is correct
7 Correct 707 ms 12152 KB Output is correct
8 Correct 505 ms 22800 KB Output is correct
9 Correct 854 ms 23156 KB Output is correct
10 Correct 2844 ms 23008 KB Output is correct