oj.uz

답안 #210117

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
210117 2020-03-16T15:04:36 Z ZwariowanyMarcin Relativnost (COCI15_relativnost) C++14
0 / 140
 3490 ms 23896 KB 
#include <bits/stdc++.h>
#define LL long long
#define LD long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep2(i, j, n) for (LL i = j; i <= n; ++i)
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define boost cin.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(), x.end()

using namespace std;

const int MOD = 1e4 + 7;
const int pod = (1 << 17);

void add(int &a, int b) {
	a += b;
	if (a >= MOD) a -= MOD;
}

int n, c, a, b, f, q;

int dp[2 * pod][21];
int x[2 * pod];

void merge(int u) {
	int p1 = 2 * u, p2 = 2 * u + 1;
	x[u] = x[p1] * x[p2] % MOD;
	rep(i, 0, c - 1) dp[u][i] = 0;
	rep(i, 0, c - 1)
		rep(j, 0, c - 1 - i)
			add(dp[u][i + j], dp[p1][i] * dp[p2][j] % MOD);
}	

void upd(int pos, int a, int b) {
	a %= MOD;
	b %= MOD;
	pos += pod;
	dp[pos][0] = b;
	dp[pos][1] = a;
	x[pos] = (a + b) % MOD;
	for (pos /= 2; pos; pos /= 2) merge(pos);
}

int main() {
	scanf ("%d%d", &n, &c);
	rep(i, 0, pod - 1) upd(i, 0, 1);
	rep(i, 1, n) {
		scanf ("%d%d", &a, &b);
		upd(i, a, b);
	}
	scanf ("%d", &q);
	while (q--) {
		scanf ("%d%d%d", &f, &a, &b);
		upd(f, a, b);
		int sum = 0;
		rep(i, 0, c - 1) add(sum, dp[1][i]);
		printf ("%d\n", (x[1] - sum + MOD) % MOD);
	}
		
		
	return 0;
}

Compilation message

relativnost.cpp: In function 'int main()':
relativnost.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &c);
  ~~~~~~^~~~~~~~~~~~~~~~
relativnost.cpp:54:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &a, &b);
   ~~~~~~^~~~~~~~~~~~~~~~
relativnost.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &q);
  ~~~~~~^~~~~~~~~~
relativnost.cpp:59:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d%d", &f, &a, &b);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 347 ms 22904 KB Output isn't correct
2 Incorrect 490 ms 22904 KB Output isn't correct
3 Incorrect 1375 ms 22940 KB Output isn't correct
4 Incorrect 503 ms 23672 KB Output isn't correct
5 Incorrect 1554 ms 23672 KB Output isn't correct
6 Incorrect 2787 ms 23696 KB Output isn't correct
7 Incorrect 1164 ms 23700 KB Output isn't correct
8 Incorrect 663 ms 23316 KB Output isn't correct
9 Incorrect 871 ms 23800 KB Output isn't correct
10 Incorrect 3490 ms 23896 KB Output isn't correct