oj.uz

Submission #646983

# Submission time Handle Problem Language Result Execution time Memory
646983 2022-10-01T09:47:37 Z Trisanu_Das Relativnost (COCI15_relativnost) C++17
140 / 140
 2803 ms 19676 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX = (1e5)+5, MOD = (1e4)+7;
 
int n, c, q, a[MAX], b[MAX], t[2*MAX][22];
void update(int x) {
	for(int i = (n+x >> 1); i >= 1; i >>= 1) {
		for(int j = 0; j <= c; ++j) t[i][j] = 0;
		for(int j = 0; j <= c; ++j) for(int k = 0; k <= c; ++k) {
			t[i][min(j+k, c)] = (t[i][min(j+k, c)] + t[i<<1][j]*t[i<<1|1][k])%MOD;
		}
	}
}
int main() {
	scanf("%d%d",&n,&c);
	for(int i = 0; i < n; ++i) scanf("%d",&t[n+i][1]), t[n+i][1] %= MOD;
	for(int i = 0; i < n; ++i) scanf("%d",&t[n+i][0]), t[n+i][0] %= MOD;
	for(int i = n-1; i >= 1; --i) {
		for(int j = 0; j <= c; ++j) t[i][j] = 0;
		for(int j = 0; j <= c; ++j) for(int k = 0; k <= c; ++k) {
			t[i][min(j+k, c)] = (t[i][min(j+k, c)] + t[i<<1][j]*t[i<<1|1][k])%MOD;
		}
	}
	scanf("%d",&q);
	for(int i, na, nb; q--; ) {
		scanf("%d%d%d",&i,&na,&nb); --i;
		memset(t[n+i], 0, sizeof(t[n+i]));
		t[n+i][1] = na%MOD, t[n+i][0] = nb%MOD;
		update(i);
		printf("%d\n", t[1][c]);
	}
}

Compilation message

relativnost.cpp: In function 'void update(int)':
relativnost.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    7 |  for(int i = (n+x >> 1); i >= 1; i >>= 1) {
      |               ~^~
relativnost.cpp: In function 'int main()':
relativnost.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d%d",&n,&c);
      |  ~~~~~^~~~~~~~~~~~~~
relativnost.cpp:16:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  for(int i = 0; i < n; ++i) scanf("%d",&t[n+i][1]), t[n+i][1] %= MOD;
      |                             ~~~~~^~~~~~~~~~~~~~~~~
relativnost.cpp:17:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  for(int i = 0; i < n; ++i) scanf("%d",&t[n+i][0]), t[n+i][0] %= MOD;
      |                             ~~~~~^~~~~~~~~~~~~~~~~
relativnost.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
relativnost.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d%d%d",&i,&na,&nb); --i;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 468 KB Output is correct
2 Correct 14 ms 472 KB Output is correct
3 Correct 21 ms 452 KB Output is correct
4 Correct 330 ms 12296 KB Output is correct
5 Correct 1169 ms 19104 KB Output is correct
6 Correct 1766 ms 19676 KB Output is correct
7 Correct 774 ms 14208 KB Output is correct
8 Correct 407 ms 19108 KB Output is correct
9 Correct 739 ms 17448 KB Output is correct
10 Correct 2803 ms 16848 KB Output is correct