oj.uz

Submission #27855

# Submission time Handle Problem Language Result Execution time Memory
27855 2017-07-14T08:46:21 Z szawinis Relativnost (COCI15_relativnost) C++14
126 / 140
 3883 ms 20148 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() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> c;
	for(int i = 0; i < n; i++) cin >> t[n+i][1], t[n+i][1] %= MOD;
	for(int i = 0; i < n; i++) cin >> 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;
		}
	}
	cin >> q;
	for(int i, na, nb; q > 0; q--) {
		cin >> i >> na >> nb; --i;
		fill(t[n+i], t[n+i]+c+1, 0);
		t[n+i][1] = na%MOD, t[n+i][0] = nb%MOD;
		update(i);
		cout << t[1][c] << endl;
	}
}

Compilation message

relativnost.cpp: In function 'void update(int)':
relativnost.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  for(int i = (n+x >> 1); i >= 1; i >>= 1) {
                ^

Subtask #1
126.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20148 KB Output is correct
2 Correct 16 ms 20148 KB Output is correct
3 Correct 26 ms 20148 KB Output is correct
4 Correct 636 ms 20148 KB Output is correct
5 Correct 1823 ms 20148 KB Output is correct
6 Correct 2566 ms 20148 KB Output is correct
7 Correct 1199 ms 20148 KB Output is correct
8 Correct 569 ms 20148 KB Output is correct
9 Correct 999 ms 20148 KB Output is correct
10 Runtime error 3883 ms 20148 KB Execution timed out (wall clock limit exceeded)