oj.uz

답안 #875449

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
875449 2023-11-19T17:44:48 Z serifefedartar Nekameleoni (COCI15_nekameleoni) C++17
140 / 140
 1193 ms 162100 KB 
#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

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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 126544 KB Output is correct
2 Correct 40 ms 126296 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 126812 KB Output is correct
2 Correct 55 ms 126912 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 128084 KB Output is correct
2 Correct 62 ms 127548 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 349 ms 133456 KB Output is correct
2 Correct 1057 ms 149252 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 556 ms 144952 KB Output is correct
2 Correct 1090 ms 159248 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 729 ms 141396 KB Output is correct
2 Correct 1190 ms 155016 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 870 ms 147724 KB Output is correct
2 Correct 1192 ms 156408 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 870 ms 146688 KB Output is correct
2 Correct 1193 ms 158196 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1146 ms 162100 KB Output is correct
2 Correct 1192 ms 161332 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1172 ms 162040 KB Output is correct
2 Correct 1173 ms 161364 KB Output is correct