vito1036's blog

By vito1036, history, 8 months ago,

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!

• +94

 » 8 months ago, # |   +19 why is there a bitset in tags ?
•  » » 8 months ago, # ^ |   +48 They're neccesary in COCI contests
 » 8 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?
•  » » 8 months ago, # ^ |   +1 +
•  » » 8 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.
 » 8 months ago, # | ← Rev. 2 →   +17 Reminder: the contest starts in one hour.
 » 8 months ago, # | ← Rev. 2 →   +4 There is $O((n+q)\log{}n)$ solution for Dizalo... HintTry to calculate which elements will affect the solution and in which period of time. How do I calculate it?Try doing it offline.Then you just need to somehow maintain solution. Code#include #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 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 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 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; } 
•  » » 8 months ago, # ^ | ← Rev. 2 →   +13 You can do it online with the same complexity. Code#include using namespace std; const int MAXN = 1e5 + 2; const int OFF = 1 << 18; int n, q, a[MAXN], inv[MAXN]; long long ans; set 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; }