oj.uz

답안 #209875

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
209875 2020-03-15T19:26:51 Z ZwariowanyMarcin Nekameleoni (COCI15_nekameleoni) C++14
140 / 140
 2126 ms 45820 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 23416 KB Output is correct
2 Correct 48 ms 23288 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 23804 KB Output is correct
2 Correct 78 ms 23544 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 24056 KB Output is correct
2 Correct 118 ms 24056 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 727 ms 27576 KB Output is correct
2 Correct 1785 ms 38264 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1012 ms 35192 KB Output is correct
2 Correct 1864 ms 43440 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1406 ms 32376 KB Output is correct
2 Correct 1945 ms 40748 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1654 ms 37752 KB Output is correct
2 Correct 1987 ms 41464 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1751 ms 36664 KB Output is correct
2 Correct 1971 ms 42616 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2058 ms 45644 KB Output is correct
2 Correct 2126 ms 45688 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2027 ms 45560 KB Output is correct
2 Correct 1988 ms 45820 KB Output is correct