oj.uz

Submission #93613

# Submission time Handle Problem Language Result Execution time Memory
93613 2019-01-10T10:30:25 Z BartolM Relativnost (COCI15_relativnost) C++17
140 / 140
 3402 ms 13152 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;

const int INF=0x3f3f3f3f;
const int N=1e5+5;
const int K=25;
const int MOD=10007;

int n, k, off=1, q;
int tour[K][3*N], A[N], B[N];

int add(int x, int y) {
    return (x+y)%MOD;
}

int mul(int x, int y) {
    return (x*y)%MOD;
}

void mrg(int l, int r, int pos) {
    for (int i=0; i<k; ++i) {
        tour[i][pos]=0;
        for (int j=0; j<=i; ++j) {
            tour[i][pos]=add(mul(tour[j][l], tour[i-j][r]), tour[i][pos]);
        }
    }
    tour[k][pos]=0;
    for (int i=0; i<=k; ++i) {
        for (int j=k-i; j<=k; ++j) {
            tour[k][pos]=add(tour[k][pos], mul(tour[i][l], tour[j][r]));
        }
    }
}

void update(int pos, int a, int b) {
    pos+=off;
    tour[0][pos]=b;
    tour[1][pos]=a;
    while (1) {
        pos/=2;
        if (!pos) break;
        mrg(pos*2, pos*2+1, pos);
    }
}

void load() {
    scanf("%d %d", &n, &k);
    while (off<n) off*=2;
    for (int i=0; i<n; ++i) {
        scanf("%d", A+i);
        A[i]%=MOD;
        tour[1][i+off]=A[i];
    }
    for (int i=0; i<n; ++i) {
        scanf("%d", B+i);
        B[i]%=MOD;
        tour[0][i+off]=B[i];
    }
    for(int i=n; i<off; ++i) tour[0][i+off] = 1;
    scanf("%d", &q);
}

void solve() {
    for (int i=off-1; i>0; --i) mrg(i*2, i*2+1, i);
    //printf("%d\n", tour[k][1]);
    for (int i=0; i<q; ++i) {
        int p, a, b;
        scanf("%d %d %d", &p, &a, &b); --p;
        update(p, a%MOD, b%MOD);
        printf("%d\n", tour[k][1]);
    }
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message

relativnost.cpp: In function 'void load()':
relativnost.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
relativnost.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", A+i);
         ~~~~~^~~~~~~~~~~
relativnost.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", B+i);
         ~~~~~^~~~~~~~~~~
relativnost.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
relativnost.cpp: In function 'void solve()':
relativnost.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &p, &a, &b); --p;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 492 KB Output is correct
2 Correct 13 ms 512 KB Output is correct
3 Correct 24 ms 624 KB Output is correct
4 Correct 377 ms 3652 KB Output is correct
5 Correct 1383 ms 9736 KB Output is correct
6 Correct 2065 ms 12224 KB Output is correct
7 Correct 848 ms 5244 KB Output is correct
8 Correct 457 ms 6904 KB Output is correct
9 Correct 869 ms 7416 KB Output is correct
10 Correct 3402 ms 13152 KB Output is correct