Submission #209875

#	Time	Username	Problem	Language	Result	Execution time	Memory
209875		ZwariowanyMarcin	Nekameleoni (COCI15_nekameleoni)	C++14	140 / 140	2126 ms	45820 KiB

nekameleoni

#include <bits/stdc++.h>
#define LL long long
#define LD long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep2(i, j, n) for (LL i = j; i <= n; ++i)
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define boost cin.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(), x.end()

using namespace std;

const int N = 1e5 + 100;
const int INF = 1e9;
const int pod = (1 << 17);

int n, k, m;
int d[N];
int a, b, e;
LL full;

struct gao {
	int ans, sum;
	vector <pair<LL, int>> pref, suf;
	
	gao() {}
	gao(LL x) {
		if (x == -1) {
			ans = INF;
			sum = 0;
			pref = suf = {};
		}
		else {
			ans = ((1LL << x) == full ? 1 : INF);
			sum = 1;
			pref = suf = {{1LL << x, 1}};
		}
	}
};

gao t[2 * pod], c;

int p, s, s2;

gao merge(const gao& a, const gao& b) {
	c.ans = min(a.ans, b.ans);
	c.pref.clear();
	c.suf.clear();
	c.sum = a.sum + b.sum;
	
	p = ss(a.suf);
	s = a.sum;
	s2 = 0;
	
	rep(i, 0, ss(b.pref) - 1) {
		while (0 <= p - 1 && (b.pref[i].fi | a.suf[p - 1].fi) == full) {
			if (p != ss(a.suf)) s -= a.suf[p].se;
			p--;
		}
		if (p != ss(a.suf)) c.ans = min(c.ans, s + s2 + 1 + (1 - a.suf[p].se));
		s2 += b.pref[i].se;
	}
	
	LL last = 0LL;
	int cnt = 0;
	
	for (auto it : a.pref) {
		if ((it.fi | last) != last) {
			if (cnt) c.pref.pb({last, cnt});
			last = it.fi | last;cnt = it.se;
		}
		else cnt += it.se;
	}
	for (auto it : b.pref) {
		if ((it.fi | last) != last) {
			if (cnt) c.pref.pb({last, cnt});
			last = it.fi | last;cnt = it.se;
		}
		else cnt += it.se;
	}
	
	c.pref.pb({last, cnt});	
	
	last = 0LL;
	cnt = 0;
	
	for (auto it : b.suf) {
		if ((it.fi | last) != last) {
			if (cnt) c.suf.pb({last, cnt});
			last = it.fi | last;cnt = it.se;
		}
		else cnt += it.se;
	}
	for (auto it : a.suf) {
		if ((it.fi | last) != last) {
			if (cnt) c.suf.pb({last, cnt});
			last = it.fi | last;cnt = it.se;
		}
		else cnt += it.se;
	}
	
	c.suf.pb({last, cnt});
	return c;	
}

void update(int x, int c) {
	x += pod;
	t[x] = gao(c);
	x /= 2;
	while (x) {
		t[x] = merge(t[2 * x], t[2 * x + 1]);
		x /= 2;
	}
}

int main() {
	scanf ("%d%d%d", &n, &k, &m);
	full = (1LL << k) - 1;
	rep(i, 1, n) {
		scanf ("%d", d + i);
		d[i]--;
	}	
	rep(i, 0, pod - 1) {
		if (1 <= i && i <= n) t[i + pod] = gao(d[i]);
		else t[i + pod] = gao(-1);
	}
	per(i, 1, pod - 1) t[i] = merge(t[2 * i], t[2 * i + 1]);
	
	while (m--) {
		scanf ("%d", &a);
		if (a == 2) {
			int w = t[1].ans;
			if (w == INF) w = -1;
			printf ("%d\n", w);
		}
		else {
			scanf ("%d%d", &b, &e);
			e--;
			update(b, e);
		}
		assert(ss(t[1].pref) <= k);
		assert(ss(t[1].suf) <= k);
	}
		
	return 0;
}

Compilation message (stderr)

nekameleoni.cpp: In function 'int main()':
nekameleoni.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d%d", &n, &k, &m);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:125:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", d + i);
   ~~~~~~^~~~~~~~~~~~~
nekameleoni.cpp:135:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &a);
   ~~~~~~^~~~~~~~~~
nekameleoni.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d%d", &b, &e);
    ~~~~~~^~~~~~~~~~~~~~~~

• 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