Submission #1265928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265928		canhnam357	Nekameleoni (COCI15_nekameleoni)	C++20	140 / 140	1336 ms	68636 KiB

nekameleoni

// source problem : 
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
#define MASK(i) (1LL << (i))
void ckmax(int& f, int s)
{
	f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
	f = (f < s ? f : s);
}
int k;
const int inf = 1e18;
struct info
{
	vector<int> pre, suf, p, s;
	int ans;
	info()
	{
		ans = 0;
	}
	info(int val, int pos)
	{
		p.push_back(pos);
		s.push_back(pos);
		pre.push_back(val);
		suf.push_back(val);
		ans = (k == 1 ? 1 : inf);
	}
};
info operator+(info a, info b)
{
	if (!a.ans) return b;
	if (!b.ans) return a;
	info res;
	res.ans = min(a.ans, b.ans);
	res.pre = a.pre;
	res.p = a.p;
	for (int i = 0; i < b.pre.size(); i++)
	{
		int x = b.pre[i] | res.pre.back();
		if (x != res.pre.back())
		{
			res.pre.push_back(x);
			res.p.push_back(b.p[i]);
		}
	}
	res.suf = b.suf;
	res.s = b.s;
	for (int i = 0; i < a.suf.size(); i++)
	{
		int x = a.suf[i] | res.suf.back();
		if (x != res.suf.back())
		{
			res.suf.push_back(x);
			res.s.push_back(a.s[i]);
		}
	}
	int i = a.suf.size() - 1;
	for (int j = 0; j < b.pre.size(); j++)
	{
		while (i >= 0 && (b.pre[j] | a.suf[i]) == MASK(k) - 1) i--;
		if (i != a.suf.size() - 1)
		{
			ckmin(res.ans, b.p[j] - a.s[i + 1] + 1);
		}
	}
	return res;
}
vector<int> a;
info st[1 << 18];
void build(int id = 1, int l = 1, int r = 1 << 17)
{
	if (l == r)
	{
		if (l <= a.size()) st[id] = info(MASK(a[l - 1]), l);
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	st[id] = st[id << 1] + st[id << 1 | 1];
}
void update(int pos, int val, int id = 1, int l = 1, int r = 1 << 17)
{
	if (pos < l || pos > r) return;
	if (l == r)
	{
		st[id] = info(val, pos);
		return;
	}
	int mid = (l + r) >> 1;
	update(pos, val, id << 1, l, mid);
	update(pos, val, id << 1 | 1, mid + 1, r);
	st[id] = st[id << 1] + st[id << 1 | 1];
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> k >> q;
	a.resize(n);
	for (int &i : a) cin >> i, i--;
	build();
	while (q--)
	{
		int t;
		cin >> t;
		if (t == 2)
		{
			int x = st[1].ans;
			cout << (x > n ? -1LL : x) << '\n';
		}
		else
		{
			int p, x;
			cin >> p >> x;
			x--;
			update(p, MASK(x));
		}
	}
	return 0;
}

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