oj.uz

Submission #98671

# Submission time Handle Problem Language Result Execution time Memory
98671 2019-02-25T03:35:14 Z long10024070 Relativnost (COCI15_relativnost) C++11
140 / 140
 3941 ms 25232 KB 
#define Link ""

#include <iostream>
#include <cstdio>
#include <array>

#define TASK "RELATIVNOST"

using namespace std;

const int Mod = 1e4 + 7;
const int maxn = 1e5 + 10;
const int maxc = 21;
array <int,maxc> None;
int n,c,a[maxn],b[maxn],q;
struct T_node
{
    int l,r;
    array <int,maxc> val;
} node[maxn*6];

void Enter()
{
    cin >> n >> c;
    for (int i=1;i<=n;++i) {
        cin >> a[i];
        a[i] %= Mod;
    }
    for (int i=1;i<=n;++i) {
        cin >> b[i];
        b[i] %= Mod;
    }
}

void Init()
{
    fill(None.begin(),None.end(),0);
    None[0] = 1;
}

array <int,maxc> operator + (array <int,maxc> a, array <int,maxc> b)
{
    array <int,maxc> res;
    fill(res.begin(),res.end(),0);
    long long s = 0;
    for (int i=0;i<=c;++i)
        for (int j=0;j<=c;++j)
            if (i + j < c)
                res[i+j] += a[i] * b[j];
            else
                s += a[i] * b[j];
    for (int i=0;i<c;++i)
        res[i] %= Mod;
    res[c] = s % Mod;
    return res;
}

void Build_tree(int i, int l, int r)
{
    node[i].l = l;
    node[i].r = r;
    if (l != r) {
        Build_tree(i*2,l,(l+r)/2);
        Build_tree(i*2+1,(l+r)/2+1,r);
        node[i].val = node[i*2].val + node[i*2+1].val;
    }
    else {
        node[i].val[0] = b[l];
        node[i].val[1] = a[l];
    }
}

void Update(int i, int id)
{
    if (node[i].r < id || id < node[i].l)
        return;
    if (node[i].l == node[i].r) {
        node[i].val[0] = b[id];
        node[i].val[1] = a[id];
    }
    else {
        Update(i*2,id);
        Update(i*2+1,id);
        node[i].val = node[i*2].val + node[i*2+1].val;
    }
}

array <int,maxc> Query(int i, int l, int r)
{
    if (node[i].r < l || r < node[i].l)
        return None;
    if (l <= node[i].l && node[i].r <= r)
        return node[i].val;
    else
        return Query(i*2,l,r) + Query(i*2+1,l,r);
}

void Solve()
{
    Build_tree(1,1,n);
    for (cin>>q;q>0;--q) {
        int p,_a,_b;
        cin >> p >> _a >> _b;
        a[p] = _a % Mod;
        b[p] = _b % Mod;
        Update(1,p);
        array <int,maxc> Left = Query(1,1,p-1);
        array <int,maxc> Mid = Query(1,p,p);
        array <int,maxc> Right = Query(1,p+1,n);
        array <int,maxc> res = Left + Mid + Right;
        cout << res[c] << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

#ifdef LHL
    freopen(".INP","r",stdin);
    freopen(".OUT","w",stdout);
#else
//    freopen(TASK".INP","r",stdin);
//    freopen(TASK".OUT","w",stdout);
#endif // LHL

    Enter();
    Init();
    Solve();
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 512 KB Output is correct
2 Correct 15 ms 512 KB Output is correct
3 Correct 33 ms 512 KB Output is correct
4 Correct 648 ms 13012 KB Output is correct
5 Correct 1946 ms 25208 KB Output is correct
6 Correct 2452 ms 25012 KB Output is correct
7 Correct 1428 ms 13036 KB Output is correct
8 Correct 765 ms 24824 KB Output is correct
9 Correct 1476 ms 25232 KB Output is correct
10 Correct 3941 ms 25052 KB Output is correct