Croatian Open Competition in Informatics (COCI) 2023/2024

→ Pay attention

Before contest
Educational Codeforces Round 173 (Rated for Div. 2)
39:09:16
Register now »

→ Streams

By aryanc403

Before stream 41:19:15

View all →

→ Top rated

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

View all →

→ Find user

→ Recent actions

Detailed →

vito1036's blog

Croatian Open Competition in Informatics (COCI) 2023/2024 — Round #2

By vito1036, history, 13 months ago, In English

Hi everyone!

The second round of COCI will be held this Saturday, December 2nd at 14:00 UTC. You can access the judging system here. If you are not familiar with COCI contest format, we encourage you to read the announcement.

The round was prepared by ToniB, Agnus, fbabic, mlicul and me.

Feel free to discuss the problems in the comment section after the contest ends.

Hope to see you and good luck!

coci, contest, croatia, bitset

vito1036
13 months ago
17

Comments (15)

Show archived | Write comment?

Mamed0v

13 months ago, # |

+19

why is there a bitset in tags ?

→ Reply

Aliyyiakbar

13 months ago, # ^ |

+48

They're neccesary in COCI contests

→ Reply

terracottalite

13 months ago, # |

← Rev. 2 →

+19

The judge and https://hsin.hr/coci/ conflict about the start time? It seems the judge is crotia time and the announcment page is UTC, but both say 14.00. Can you clarify this?

→ Reply

Abito

13 months ago, # ^ |

→ Reply

vito1036

13 months ago, # ^ |

← Rev. 2 →

+11

Thanks for the info! The judge starting time is wrong. The round will start at 14:00 UTC. UPD: it's fixed now.

→ Reply

vito1036

13 months ago, # |

← Rev. 2 →

+17

Reminder: the contest starts in one hour.

→ Reply

WeaponizedAutist

13 months ago, # |

← Rev. 2 →

Feedback:

Task 1: Meh
Task 2: Meh
Task 3: Cute task, enjoyed it.
Task 4: A bit standard, but ok. Perhaps this should have had slightly less points?
Task 5: Again, a bit standard but a decent educational problem.

Overall, problems were good quality and educational, kind of like old style cf problems. The contest would have been more enjoyable if either task 1 or task 2 was replaced by a harder problem.

Edit: Also, the tests for task 3 might be a bit weak. My first submission had a very critical bug (which was not dependent on n) but it passed all test cases of the first 3 subtasks and 13/15 test cases of the last subtask.

→ Reply

NeroZein

13 months ago, # |

+19

This is the first time I AK an OI contest, it feels amazing !

I feel problems are a little bit easier than usual, but I still enjoyed the contest, well done.

→ Reply

dimash1

13 months ago, # |

where can i upsolve?

→ Reply

AndiR

13 months ago, # ^ |

https://evaluator.hsin.hr/tasks/

HONI -> 2023./2024. -> 2. kolo

→ Reply

DinoHadzic

13 months ago, # |

← Rev. 2 →

There is $$$O((n+q)\log{}n)$$$ solution for Dizalo...

Hint

Code

#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef pair <int, int> pii;

const int N = 1e5 + 7, inf = 1e9, ofs = (1 << 17);

int n, q;
int a[N], ti[N], va[N];
bool spe[N], del[N];
vector <int> wh[N];

struct fe {
	int fen[N] = {0};
	void Add(int x, int val) {for (; x < N; x += x & -x) fen[x] += val;}
	int Query(int x) {int out = 0; for (; x; x -= x & -x) out += fen[x]; return out;}
};

int t[2*ofs];
void Update(int x, int val) {
	x += ofs; t[x] = val;
	while (x /= 2) t[x] = max(t[2*x], t[2*x+1]);
}
int Query(int x, int l, int r, int lo = 0, int hi = ofs-1) {
	if (r < lo || hi < l) return 0;
	if (l <= lo && hi <= r) return t[x];
	int mid = (lo+hi)/2;
	return max(Query(2*x, l, r, lo, mid), Query(2*x+1, l, r, mid+1, hi));
}

int main () {
	FIO;
	cin >> n >> q;
	
	fe f1, f2, f3;
	
	for (int i = 1; i <= n; i++) ti[i] = q+1;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		ti[i] = q+1;
		f1.Add(i, 1);
		f2.Add(i, 1);
	}
	for (int i = 1; i <= q; i++) {
		cin >> va[i];
		ti[va[i]] = i;
	}
	
	for (int i = n; i; i--) {
		wh[Query(1, 0, a[i]-1)].pb(i);
		Update(a[i], ti[i]);
	}
	
	ll sum = 0;
	set <pii> s;
	s.insert({0, 0}); s.insert({n+1, n+1});
	
	for (auto y : wh[0]) {
		sum += y-a[y];
		f3.Add(y, 1);
		spe[y] = 1;
		s.insert({a[y], y});
	}
	
	cout << sum+n << " ";
	for (int j = 1; j <= q; j++) {
		int x = va[j];
		del[x] = 1;
		
		if (spe[x]) {
			f3.Add(x, -1);
			sum -= f1.Query(x) - f2.Query(a[x]);
			s.erase({a[x], x});
		}
		else sum -= f3.Query((--s.lower_bound({a[x], 0})) -> S) - f3.Query(x);
		f1.Add(x, -1);
		f2.Add(a[x], -1);
		
		for (auto y : wh[j]) {
			if (del[y]) continue;
			spe[y] = 1;
			f3.Add(y, 1);
			s.insert({a[y], y});
			sum += f1.Query(y) - f2.Query(a[y]);
		}
		
		cout << sum+n-j << " ";
	}

	return 0;
}

→ Reply

ToniB

13 months ago, # ^ |

← Rev. 2 →

+13

You can do it online with the same complexity.

Code

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 2;
const int OFF = 1 << 18;

int n, q, a[MAXN], inv[MAXN];
long long ans;
set<int> suffix_min;

struct Fenwick {
	int fen[MAXN] = {0};

	void add(int x, int val = 1) {
		for (++x; x <= n; x += x & -x) fen[x] += val;
	}
	int count(int x) {
		int ret = 0;
		for (++x; x; x -= x & -x) ret += fen[x];
		return ret;
	}
	int count(int l, int r) {
		return count(r) - count(l - 1);
	}

} removed_values, removed_indices, marked_values, marked_indices;

struct Tournament {
	int tour[OFF] = {0};

	void update(int i, int val, int x = 0, int l = 0, int r = n - 1) {
		if (l > i || r < i) return ;
		if (l == r) {
			tour[x] = val; return ;
		}
		int mid = (l + r) >> 1;
		update(i, val, x * 2 + 1, l, mid);
		update(i, val, x * 2 + 2, mid + 1, r);

		tour[x] = min(tour[x * 2 + 1], tour[x * 2 + 2]);
	}

	int query(int ql, int qr, int x = 0, int l = 0, int r = n - 1) {
		if (ql <= l && r <= qr) return tour[x];
		if (ql > r || l > qr) return n;

		int mid = (l + r) >> 1;
		return min(query(ql, qr, x * 2 + 1, l, mid), query(ql, qr, x * 2 + 2, mid + 1, r));
	}

} values;

void mark(int i) {
	suffix_min.insert(i);
	marked_indices.add(i);
	marked_values.add(a[i]);

	ans += (i - removed_indices.count(i)) - (a[i] - removed_values.count(a[i]));
}

void unmark(int i) {
	ans -= (i - removed_indices.count(i)) - (a[i] - removed_values.count(a[i]));
	marked_indices.add(i, -1);
	marked_values.add(a[i], -1);

	int L = n, R = 0;
	auto it = suffix_min.find(i);

	if (++it != suffix_min.end()) R = *it;
	else R = n;
	--it;

	if (it != suffix_min.begin()) L = (*--it) + 1;
	else L = 0;

	suffix_min.erase(suffix_min.find(i));

	while (L < R) {
		int j = values.query(L, R - 1);
		if (j == n) break;

		j = inv[j];
		if (a[j] < ((R == n) ? n : a[R])) mark(j);

		L = j + 1;
	}

}

int main() {

	cin >> n >> q;

	for (int i = 0; i < n; ++i) {
		cin >> a[i], --a[i];

		values.update(i, a[i]);
		inv[a[i]] = i;
	}

	int cur = n;
	for (int i = n - 1; i >= 0; --i) {
		cur = min(cur, a[i]);
		if (cur == a[i]) {
			mark(i);
		}
	}

	ans += n;
	cout << ans << " ";

	while (q--) {
		int i;
		cin >> i, --i;

		values.update(i, n);

		if (suffix_min.count(i)) unmark(i);

		ans += marked_values.count(a[i], n - 1);
		ans -= marked_indices.count(i, n - 1);

		removed_values.add(a[i]);
		removed_indices.add(i);

		--ans;
		cout << ans << " ";
	}

	return 0;
}

→ Reply

XuYueming

11 months ago, # ^ |

You will get a RE because you erase the end of a set.(in line.77). Or please explain why.

→ Reply

XuYueming

11 months ago, # ^ |

← Rev. 2 →

Oh, i am stupid, now i understand, sorry.

→ Reply

ToniB

11 months ago, # ^ |

The if statement on line 69 has a condition that will always be true, perhaps this caused the confusion.

I'm not sure why I put it there, since it is completely redundant. Thanks for pointing this out (the code is edited now).

→ Reply