oj.uz

답안 #252671

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
252671 2020-07-26T06:07:39 Z islingr Nekameleoni (COCI15_nekameleoni) C++14
14 / 140
 3000 ms 421388 KB 
#include <iostream>
#include <cassert>

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define f first
#define s second

using namespace std;
using ll = int64_t;

const int N = 1 << 17, K = 51, inf = 1e9;
int U, sz, k;

struct S {
	int len, ans;
	pair<ll, int> pref[K], suff[K];
	S() : len{0}, ans{inf} { }
	S(int p, int v) : len{1}, ans{U != 1 ? inf : 1} {
		pref[0] = suff[0] = {1ll << v, p};
	}
	S(const S &l, const S &r) : ans{min(l.ans, r.ans)} {
		len = 0;
		rep(i, 0, l.len) pref[len++] = l.pref[i];
		rep(i, 0, r.len)
			if (len) {
				pref[len] = r.pref[i];
				pref[len].f |= pref[len - 1].f;
				if (pref[len].f != pref[len - 1].f) ++len;
			} else pref[len++] = r.pref[i];
		int tmp = len;

		len = 0;
		rep(i, 0, r.len) suff[len++] = r.suff[i];
		rep(i, 0, l.len)
			if (len) {
				suff[len] = l.suff[i];
				suff[len].f |= suff[len - 1].f;
				if (suff[len].f != suff[len - 1].f) ++len;
			} else suff[len++] = l.suff[i];
		assert(tmp == len);
		assert(len <= k);
		assert(len < K);

		rep(s, 0, l.len)
			rep(p, 0, r.len)
				if ((l.suff[s].f | r.pref[p].f) == U)
					ans = min(ans, r.pref[p].s - l.suff[s].s + 1);
	}
} t[N << 1];

int query() { return t[1].ans; }
void update(int p, int v) {
	p += sz;
	for (t[p] = {p, v}; p >>= 1; )
		t[p] = {t[p << 1], t[p << 1|1]};
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, q; cin >> n >> k >> q; U = (1ll << k) - 1;
	for (sz = 1; sz < n; sz <<= 1);
	assert(sz <= N);
	
	rep(i, 0, n) { int v; cin >> v; --v; update(i, v); }
	while (q--) {
		short t; cin >> t; --t;
		if (t) cout << (query() != inf ? query() : -1) << '\n';
		else {
			int p, v; cin >> p >> v; --p; --v;
			update(p, v);
		}
	}
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 275 ms 420988 KB Output is correct
2 Correct 269 ms 420984 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 307 ms 420984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 401 ms 420984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1579 ms 420984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2705 ms 421244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3083 ms 421112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3091 ms 421368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3109 ms 421388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3098 ms 421240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3118 ms 421112 KB Time limit exceeded
2 Halted 0 ms 0 KB -