oj.uz

답안 #209873

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
209873 2020-03-15T19:21:23 Z ZwariowanyMarcin Nekameleoni (COCI15_nekameleoni) C++17
42 / 140
 3000 ms 49924 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, c;
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}};
		}
	}
};

vector <pair<LL, int>> pp;

gao t[2 * pod];

gao merge(const gao& a, const gao& b) {
	gao c;
	c.ans = min(a.ans, b.ans);
	c.pref = c.suf = {};
	c.sum = a.sum + b.sum;
	
	int p = ss(a.suf);
	int s = a.sum;
	int 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;
	
	pp = a.pref;
	for (auto it : b.pref) pp.pb(it);
	
	for (auto it : pp) {
		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;
	
	pp = b.suf;
	for (auto it : a.suf) pp.pb(it);
	
	for (auto it : pp) {
		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, &c);
			c--;
			update(b, c);
		}
	}
		
	return 0;
}

Compilation message

nekameleoni.cpp: In function 'int main()':
nekameleoni.cpp:116: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:119:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", d + i);
   ~~~~~~^~~~~~~~~~~~~
nekameleoni.cpp:129:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &a);
   ~~~~~~^~~~~~~~~~
nekameleoni.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d%d", &b, &c);
    ~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 23544 KB Output is correct
2 Correct 65 ms 23420 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 23800 KB Output is correct
2 Correct 110 ms 23928 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 24184 KB Output is correct
2 Correct 191 ms 24184 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1226 ms 28536 KB Output is correct
2 Execution timed out 3098 ms 41440 KB Time limit exceeded

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1636 ms 37496 KB Output is correct
2 Execution timed out 3101 ms 47352 KB Time limit exceeded

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2333 ms 34296 KB Output is correct
2 Execution timed out 3101 ms 44152 KB Time limit exceeded

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2754 ms 40724 KB Output is correct
2 Execution timed out 3095 ms 46200 KB Time limit exceeded

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2678 ms 39416 KB Output is correct
2 Execution timed out 3099 ms 47608 KB Time limit exceeded

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3101 ms 49912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3095 ms 49924 KB Time limit exceeded
2 Halted 0 ms 0 KB -