oj.uz

Submission #401911

# Submission time Handle Problem Language Result Execution time Memory
401911 2021-05-11T01:24:21 Z idontreallyknow Vođe (COCI17_vode) C++17
72 / 120
 3000 ms 196804 KB 
#include <bits/stdc++.h>
using namespace std;
struct segtree{
	typedef int T;
	T base = 0;
	T comb(T a, T b) {
		return a+b;
	}
	int n;
	vector<T> v;
	segtree(int x): n(x) {
		v.resize(2*n+5);
	}
	void update(int i, T x) {
		i+=n;
		v[i] = x;
		for (i /= 2; i >= 1; i /= 2) {
			v[i] = comb(v[2*i], v[2*i+1]);
		}
	}
	T get(int l, int r) {
		T ans = base;
		for (l+=n, r+=n; l <= r; l/=2, r/=2) {
			if (l%2) ans = comb(ans, v[l++]);
			if ((r+1)%2) ans = comb(ans, v[r--]);
		}
		return ans;
	}
	void build(vector<T> &x) {
		for (int q = 0; q < (int)x.size(); q++) {
			v[q+n] = x[q];
		}
		for (int q = n-1; q >= 1; q--) {
			v[q] = comb(v[2*q], v[2*q+1]);
		}
	}
};
vector<segtree> st(5005,segtree(5005));
int a[5005];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,k;
	cin >> n >> m >> k;
	for (int q = 0; q < n; q++) cin >> a[q];
	for (int q = 0; q < n; q++) st[q].update(m,1-a[q]);
	for (int q = m-1; q >= 0; q--) {
		for (int w = 0; w < n; w++) {
			int e = w == n-1 ? 0 : w+1;
			int lo = q+1, hi = min(q+k,m);
			int z = st[e].get(lo,hi);
			bool win = false;
			if (a[e] == 1 && z > 0) win = true;
			if (a[e] == 0 && z < hi-lo+1) win = true;
			int res = win ? a[e] : 1 - a[e];
			st[w].update(q,res);
		}
	}
	for (int q = 0; q < n; q++) {
		int w = q == 0 ? n-1 : q-1;
		cout << st[w].get(0,0) << ' ';
	}
	cout << '\n';
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 196748 KB Output is correct
2 Correct 99 ms 196732 KB Output is correct
3 Correct 87 ms 196664 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 196716 KB Output is correct
2 Correct 86 ms 196660 KB Output is correct
3 Correct 91 ms 196680 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 196676 KB Output is correct
2 Correct 111 ms 196708 KB Output is correct
3 Correct 91 ms 196640 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 196716 KB Output is correct
2 Correct 103 ms 196728 KB Output is correct
3 Correct 101 ms 196660 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 196644 KB Output is correct
2 Correct 106 ms 196760 KB Output is correct
3 Correct 106 ms 196716 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 196676 KB Output is correct
2 Correct 105 ms 196732 KB Output is correct
3 Correct 87 ms 196676 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 196800 KB Output is correct
2 Correct 467 ms 196668 KB Output is correct
3 Execution timed out 3048 ms 196676 KB Time limit exceeded

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1103 ms 196728 KB Output is correct
2 Execution timed out 3068 ms 196680 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 196792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3089 ms 196804 KB Time limit exceeded
2 Halted 0 ms 0 KB -