Submission #919660

#	Time	Username	Problem	Language	Result	Execution time	Memory
919660		TIN	Nekameleoni (COCI15_nekameleoni)	C++17	140 / 140	983 ms	38856 KiB

nekameleoni

#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 (stderr)

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 / 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