oj.uz

답안 #31668

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31668 2017-08-30T15:31:25 Z long10024070 Relativnost (COCI15_relativnost) C++11
140 / 140
 2569 ms 18300 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned int uint;

const int MAXN = 100005;
const int MAXC = 21;
const int mod = 10007;

int n, c, q;
int a[MAXN];
int b[MAXN];
int T[2 * MAXN][MAXC];

void update(int x) {
  for (int i = 0; i <= c; ++i) T[x][i] = 0;

  for (int i = 0; i <= c; ++i)
    for (int j = 0; j <= c; ++j)
      T[x][min(i + j, c)] += (T[x * 2][i] * T[x * 2 + 1][j]) % mod;

  for (int i = 0; i <= c; ++i) T[x][i] %= mod;
}

void change(int x) {
  x += n;
  memset(T[x], 0, sizeof T[x]);
  T[x][1] = a[x - n] % mod;
  T[x][0] = b[x - n] % mod;

  for (x /= 2; x > 0; x /= 2) update(x);
}

int main(void) {
  scanf("%d%d", &n, &c);
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
  for (int i = 0; i < n; ++i) {
    T[i + n][0] = b[i] % mod;
    T[i + n][1] = a[i] % mod;
  }

  for (int i = n-1; i >= 1; --i)
    update(i);

  scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    int p;
    scanf("%d", &p); --p;
    scanf("%d%d", &a[p], &b[p]); 
    change(p);
    printf("%d\n", T[1][c]);
  }

  return 0;
}

Compilation message

relativnost.cpp: In function 'int main()':
relativnost.cpp:39:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &c);
                        ^
relativnost.cpp:40:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
                                                 ^
relativnost.cpp:41:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
                                                 ^
relativnost.cpp:50:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
                  ^
relativnost.cpp:53:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p); --p;
                    ^
relativnost.cpp:54:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &a[p], &b[p]); 
                                ^

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18300 KB Output is correct
2 Correct 6 ms 18300 KB Output is correct
3 Correct 16 ms 18300 KB Output is correct
4 Correct 403 ms 18300 KB Output is correct
5 Correct 1163 ms 18300 KB Output is correct
6 Correct 1669 ms 18300 KB Output is correct
7 Correct 779 ms 18300 KB Output is correct
8 Correct 463 ms 18300 KB Output is correct
9 Correct 756 ms 18300 KB Output is correct
10 Correct 2569 ms 18300 KB Output is correct