Submission #252547

#	Time	Username	Problem	Language	Result	Execution time	Memory
252547		islingr	Nekameleoni (COCI15_nekameleoni)	C++14	0 / 140	2164 ms	422332 KiB

nekameleoni

#include <bits/stdc++.h>

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

using namespace std;
using ll = long long;

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

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }

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

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

		ans = inf;
		for (int s = l.len, p = 0; s--; ) {
			while (p < r.len && (l.suff[s].f | r.pref[p].f) != U) ++p;
			if (p < r.len && (l.suff[s].f | r.pref[p].f) == U)
				ckmin(ans, r.pref[p].s - l.suff[s].s + 1);
		}
	}
};

int sz = 1;
S 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, k, q; cin >> n >> k >> q; U = (1ll << k) - 1;
	while (sz < n) sz <<= 1;
	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);
		}
	}
}

Compilation message (stderr)

nekameleoni.cpp: In constructor 'S::S()':
nekameleoni.cpp:16:11: warning: 'S::ans' will be initialized after [-Wreorder]
  int len, ans;
           ^~~
nekameleoni.cpp:16:6: warning:   'int S::len' [-Wreorder]
  int len, ans;
      ^~~
nekameleoni.cpp:18:2: warning:   when initialized here [-Wreorder]
  S() : ans{inf}, len{0} { }
  ^

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14