oj.uz

Submission #209872

# Submission time Handle Problem Language Result Execution time Memory
209872 2020-03-15T19:15:59 Z ZwariowanyMarcin Nekameleoni (COCI15_nekameleoni) C++17
42 / 140
 3000 ms 51504 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}};
		}
	}
};

gao t[2 * pod];

gao merge(gao a, 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;
	
	vector <pair<LL, int>> 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:114: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:117:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", d + i);
   ~~~~~~^~~~~~~~~~~~~
nekameleoni.cpp:127:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &a);
   ~~~~~~^~~~~~~~~~
nekameleoni.cpp:134: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

# Verdict Execution time Memory Grader output
1 Correct 99 ms 23672 KB Output is correct
2 Correct 103 ms 23416 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 23932 KB Output is correct
2 Correct 168 ms 23928 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 24312 KB Output is correct
2 Correct 254 ms 24312 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1547 ms 29116 KB Output is correct
2 Execution timed out 3092 ms 42628 KB Time limit exceeded

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2058 ms 38380 KB Output is correct
2 Execution timed out 3098 ms 48760 KB Time limit exceeded

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2991 ms 35424 KB Output is correct
2 Execution timed out 3100 ms 45304 KB Time limit exceeded

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3049 ms 41780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3082 ms 40440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 51504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3085 ms 51340 KB Time limit exceeded
2 Halted 0 ms 0 KB -