Croatian Open Competition in Informatics (COCI) 2023/2024

→ Обратите внимание

До соревнования
Codeforces Round 987 (Div. 2)
19:34:36
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Codeforces Round 987 (Div 2) - Solution Discussion

Shayan

До начала 21:39:35

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
4	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
8	Dominater069	154
8	nor	154

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя vito1036

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

Автор vito1036, история, 12 месяцев назад, По-английски

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
12 месяцев назад
17

Комментарии (17)

Написать комментарий?

amin_2008

12 месяцев назад, # |

+19

why is there a bitset in tags ?

→ Ответить

Aliyyiakbar

12 месяцев назад, # ^ |

+48

They're neccesary in COCI contests

→ Ответить

terracottalite

11 месяцев назад, # |

← 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?

→ Ответить

Abito

11 месяцев назад, # ^ |

→ Ответить

vito1036

11 месяцев назад, # ^ |

← 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.

→ Ответить

vito1036

11 месяцев назад, # |

← Rev. 2 →

+17

Reminder: the contest starts in one hour.

→ Ответить

WeaponizedAutist

11 месяцев назад, # |

← 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.

→ Ответить

NeroZein

11 месяцев назад, # |

+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.

→ Ответить

Tima19

11 месяцев назад, # |

where can i upsolve?

→ Ответить

AndiR

11 месяцев назад, # ^ |

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

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

→ Ответить

Halym2007

11 месяцев назад, # |

← Rev. 2 →

Problems was very good.But I solved 1-st problem full.other problems I got some subtasks.Can you share your idea for problems?

→ Ответить

DinoHadzic

11 месяцев назад, # |

← 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;
}

→ Ответить

ToniB

11 месяцев назад, # ^ |

← 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;
}

→ Ответить