oj.uz

Submission #919660

# Submission time Handle Problem Language Result Execution time Memory
919660 2024-02-01T11:06:32 Z TIN Nekameleoni (COCI15_nekameleoni) C++17
140 / 140
 983 ms 38856 KB 
#include <bits/stdc++.h>

using namespace std;

#define FNAME "test"

#define sz(v) (int) (v).size()
#define all(v) (v).begin(), (v).end()

typedef long long ll;

const int N = 1e5 + 5;
const int oo = 1e9 + 1;

int n, k, m;
int a[N];

struct SegmentTree {
	struct Node {
		int best;
		vector<int> pre, suf;

		Node() {}

		Node(int pos) {
			best = oo;
			pre.push_back(pos);
			suf.push_back(pos);
		}

		Node(int best, vector<int> pre, vector<int> suf) : best(best), pre(pre), suf(suf) {}

		ll bit(int x) { return (1LL << x); }

		ll calc(vector<int>& vpos) {
			ll mask = 0;
			for (auto pos : vpos) mask |= bit(a[pos]);
			return mask;
		}

		Node operator + (Node const& oth) {
			vector<int> vpre = pre, vsuf = oth.suf;
			int tbest = min(best, oth.best);

			if (sz(vpre) < k) {
				ll mask = calc(vpre);
				for (int pos : oth.pre) {
					if ((mask | bit(a[pos])) != mask) {
						mask |= bit(a[pos]);
						vpre.push_back(pos);
					}
				}
			}

			if (sz(vsuf) < k) {
				ll mask = calc(vsuf);
				for (int pos : suf) {
					if ((mask | bit(a[pos])) != mask) {
						mask |= bit(a[pos]);
						vsuf.push_back(pos);
					}
				}
			}

			vector<int> cnt(k, 0);
			vector<int> tmp = suf;
			reverse(all(tmp));
			tmp.insert(tmp.end(), all(oth.pre));

			int diff = 0, j = -1;
			for (int i = 0; i < sz(tmp); i++) {
				if (j < i) {
					j = i;
					++cnt[a[tmp[i]]];
					diff = 1;
				}
				while (j + 1 < sz(tmp) && diff < k) {
					++j;
					++cnt[a[tmp[j]]];
					if (cnt[a[tmp[j]]] == 1) ++diff;
				}
				if (diff != k) break;
				tbest = min(tbest, tmp[j] - tmp[i] + 1);
				--cnt[a[tmp[i]]];
				if (cnt[a[tmp[i]]] == 0) --diff;
			}

			return Node(tbest, vpre, vsuf);
		}
	};

	Node ST[4 * N];

	void build(int id, int l, int r) {
		if (l == r) {
			ST[id] = Node(l);
			return;
		}
		int m = (l + r) / 2;
		build(id * 2, l, m);
		build(id * 2 + 1, m + 1, r);
		ST[id] = ST[id * 2] + ST[id * 2 + 1];
	}

	void update(int id, int l, int r, int pos, int val) {
		if (pos < l || r < pos) return;
		if (l == r) {
			a[pos] = val;
			ST[id] = Node(pos);
			return;
		}
		int m = (l + r) / 2;
		if (pos <= m) update(id * 2, l, m, pos, val);
		else update(id * 2 + 1, m + 1, r, pos, val);
		ST[id] = ST[id * 2] + ST[id * 2 + 1];
	}
} ST;

void Task() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cout << fixed << setprecision(9);
	if (fopen(FNAME".inp","r")) {
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

void Solve() {
	//Your Code
	cin >> n >> k >> m;
	for (int i = 1; i <= n; i++) cin >> a[i], a[i]--;
	ST.build(1, 1, n);
	while (m--) {
		int t;
		cin >> t;
		if (t == 1) {
			int pos, val;
			cin >> pos >> val;
			val--;
			ST.update(1, 1, n, pos, val);
		} else {
			int ans = ST.ST[1].best;
			if (ans == oo) ans = -1;
			cout << ans << '\n';
		}
	}
}

int main() {
	Task();
	Solve();
	cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms";
	return 37^37;
}

Compilation message

nekameleoni.cpp: In function 'void Task()':
nekameleoni.cpp:124:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |   freopen(FNAME".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:125:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |   freopen(FNAME".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 22876 KB Output is correct
2 Correct 16 ms 22620 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 22888 KB Output is correct
2 Correct 28 ms 22876 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 23132 KB Output is correct
2 Correct 38 ms 23132 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 25952 KB Output is correct
2 Correct 849 ms 34132 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 31244 KB Output is correct
2 Correct 913 ms 37324 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 29268 KB Output is correct
2 Correct 902 ms 35612 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 33276 KB Output is correct
2 Correct 983 ms 36196 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 32372 KB Output is correct
2 Correct 916 ms 36948 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 921 ms 38776 KB Output is correct
2 Correct 971 ms 38856 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 886 ms 38748 KB Output is correct
2 Correct 980 ms 38388 KB Output is correct