Submission #875449

#	Time	Username	Problem	Language	Result	Execution time	Memory
875449		serifefedartar	Nekameleoni (COCI15_nekameleoni)	C++17	140 / 140	1193 ms	162100 KiB

nekameleoni

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20; 
const ll MAXN = 5e5 + 101;

struct Node {
	int ans, l, r;
	vector<pair<ll,int>> toLeft, toRight;
	Node() { }
};

vector<int> A;
Node sg[4*MAXN];
ll K;

Node merge(Node a, Node b) {
	Node new_node;
	new_node.l = a.l;
	new_node.r = b.r;
	new_node.ans = min(a.ans, b.ans);

	int L = 0; // a.mask_left doğru gidecek
	for (int R = b.toRight.size() - 1; R >= 0; R--) {
		while (L < a.toLeft.size() && (a.toLeft[L].f | b.toRight[R].f) != (1LL<<K) - 1)
			L++;

		if ((L < a.toLeft.size()) && ((a.toLeft[L].f | b.toRight[R].f) == (1LL<<K) - 1))
			new_node.ans = min(new_node.ans, b.toRight[R].s - a.toLeft[L].s + 1);
	}

	for (auto u : a.toRight)
		new_node.toRight.push_back(u);
	for (auto u : b.toRight) {
		if (new_node.toRight.back().f != (a.toRight.back().f | u.f))
			new_node.toRight.push_back({(a.toRight.back().f | u.f), u.s});
	}
	for (auto u : b.toLeft)
		new_node.toLeft.push_back(u);
	for (auto u : a.toLeft) {
		if (new_node.toLeft.back().f != (b.toLeft.back().f | u.f))
			new_node.toLeft.push_back({(b.toLeft.back().f | u.f), u.s});
	}
	return new_node;
}

void init(int k, int a, int b) {
	if (a == b) {
		sg[k].l = a;
		sg[k].r = b;
		sg[k].toLeft.push_back({1LL << A[a], a});
		sg[k].toRight.push_back({1LL << A[a], a});
		sg[k].ans = (K == 1 ? 1 : 1e8);
		return ;
	}
	init(2*k, a, (a+b)/2);
	init(2*k+1, (a+b)/2+1, b);
	sg[k] = merge(sg[2*k], sg[2*k+1]);
}

void update(int k, int a, int b, int plc, int val) {
	if (b < plc || a > plc)
		return ;
	if (a == b) {
		sg[k].toLeft.clear();
		sg[k].toRight.clear(); 
		sg[k].toLeft.push_back({1LL << val, a});
		sg[k].toRight.push_back({1LL << val, a});
		return ;
	}
	update(2*k, a, (a+b)/2, plc, val);
	update(2*k+1, (a+b)/2+1, b, plc, val);
	sg[k] = merge(sg[2*k], sg[2*k+1]);
}

int main() {
	fast
	int N, M;
	cin >> N >> K >> M;

	A = vector<int>(N+1);
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		A[i]--;
	}
	init(1, 1, N);

	for (int i = 1; i <= M; i++) {
		int q, p, v;
		cin >> q;
		if (q == 1) {
			cin >> p >> v;
			v--;
			update(1, 1, N, p, v);
		} else 
			cout << (sg[1].ans >= 1e8 ? -1 : sg[1].ans) << "\n";
	}
}

Compilation message (stderr)

nekameleoni.cpp: In function 'Node merge(Node, Node)':
nekameleoni.cpp:30:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   while (L < a.toLeft.size() && (a.toLeft[L].f | b.toRight[R].f) != (1LL<<K) - 1)
      |          ~~^~~~~~~~~~~~~~~~~
nekameleoni.cpp:33:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   if ((L < a.toLeft.size()) && ((a.toLeft[L].f | b.toRight[R].f) == (1LL<<K) - 1))
      |        ~~^~~~~~~~~~~~~~~~~

• 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