oj.uz

답안 #98639

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98639 2019-02-25T02:20:59 Z Tieuphong Relativnost (COCI15_relativnost) C++11
42 / 140
 908 ms 33792 KB 
/***************************************************************************/
/**********************  LANG TU HAO HOA  **********************************/
/***************************************************************************/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define sz(x) ((int) x.size())
#define PB push_back
#define PF push_front
#define MP make_pair
#define ll long long
#define F first
#define S second
#define maxc 1000000007
#define MOD 10007
#define base 107
#define eps 1e-6
#define pi acos(-1)
#define N 100005
#define C 22
#define task ""
#define remain(x) ((x > MOD) ? (x - MOD) : x)

using namespace std;

int n, c, a[N], b[N], q;

struct IT
{
    ll t[N<<2][2*C], total[N<<2];

    void Upd(int l, int r, int id, int x)
    {
        if (l > x || r < x) return;
        if (l == r)
        {
            t[id][0] = b[x];
            t[id][1] = a[x];
            total[id] = (a[x]+b[x]) % MOD;
            return;
        }
        int mid = (l + r) >> 1;
        Upd(l, mid, id*2, x);
        Upd(mid+1, r, id*2+1, x);
        FOR(i, 0, c-1) t[id][i] = 0;
        FOR(i, 0, c-1)
            FOR(j, 0, c-1)
                t[id][i+j] += (t[id*2][i] * t[id*2+1][j]) % MOD;
        total[id] = (total[id*2] * total[id*2+1]) % MOD;
    }

    ll Get()
    {
        ll res = total[1];
        FOR(i, 0, c-1)
             res = (res - t[1][i] + 1ll*MOD*MOD) % MOD;
        return res;
    }
} Tree;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);
    cin >> n >> c;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) cin >> b[i];
    FOR(i, 1, n) Tree.Upd(1, n, 1, i);
    cin >> q;
    while (q--)
    {
        int pos, x, y;
        cin >> pos >> x >> y;
        a[pos] = x;
        b[pos] = y;
        Tree.Upd(1, n, 1, pos);
        cout << Tree.Get() << '\n';
    }
    return 0;
}

Subtask #1
42.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 1152 KB Output is correct
2 Correct 18 ms 1152 KB Output is correct
3 Correct 34 ms 1068 KB Output is correct
4 Runtime error 169 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 395 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 743 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 459 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 222 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 194 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 908 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)