Submission #680567

#TimeUsernameProblemLanguageResultExecution timeMemory
680567nutellaBubble Sort 2 (JOI18_bubblesort2)C++17
60 / 100
901 ms26568 KiB
#include <bits/stdc++.h> #include "bubblesort2.h" using namespace std; mt19937 rnd(228); struct Info { int mx = 0; Info() = default; explicit Info(int x) : mx(x) {} }; Info operator+(Info a, Info b) { return Info{max(a.mx, b.mx)}; } struct Tag { int add = 0; Tag() = default; explicit Tag(int x) : add(x) {} }; void apply(Info &a, Tag &b) { a.mx += b.add; } void apply(Tag &a, Tag &b) { a.add += b.add; } using key_type = pair<int, int>; struct Node { int y = 0, sz = 0; key_type key{}; Info mine{}, subtree{}; Tag tag{}; int L = 0, R = 0; Node() = default; Node(int prior, key_type key, int siz, Info val) : y(prior), key(key), sz(siz), mine(val), subtree(val) {} }; void apply(Node &x, Tag &b) { apply(x.tag, b); apply(x.mine, b); apply(x.subtree, b); } vector<Node> t{{}}; int create(Node b = Node()) { t.emplace_back(b); return t.size() - 1; } void apply(int x, Tag b) { apply(t[x], b); } void push(int x) { apply(t[x].L, t[x].tag); apply(t[x].R, t[x].tag); t[x].tag = Tag(); } void pull(int x) { t[x].sz = 1 + t[t[x].L].sz + t[t[x].R].sz; t[x].subtree = t[t[x].L].subtree + t[x].mine + t[t[x].R].subtree; } int merge(int l, int r) { if (!l || !r) return l ^ r; push(l), push(r); if (t[l].y > t[r].y) { t[l].R = merge(t[l].R, r); pull(l); return l; } else { t[r].L = merge(l, t[r].L); pull(r); return r; } } //key <= k pair<int, int> split_key(int x, key_type k) { if (!x) return {}; push(x); if (t[x].key > k) { auto se = split_key(t[x].L, k); t[x].L = se.second; pull(x); return {se.first, x}; } else { auto se = split_key(t[x].R, k); t[x].R = se.first; pull(x); return {x, se.second}; } } //left contains siz pair<int, int> split_sz(int x, int siz) { if (!x) return {}; push(x); if (t[t[x].L].sz >= siz) { auto se = split_sz(t[x].L, siz); t[x].L = se.second; pull(x); return {se.first, x}; } else { auto se = split_sz(t[x].R, siz - t[t[x].L].sz - 1); t[x].R = se.first; pull(x); return {x, se.second}; } } void debug_node(int x, string pref = "") { if (!x) { return; } pref += "->" + to_string(x); debug_node(t[x].L, pref); cout << pref << endl; debug_node(t[x].R, pref); } std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V) { int Q = X.size(), n = A.size(); int root = 0; auto insert = [&](int i) { auto [L, R] = split_key(root, {A[i], i}); Node now = Node(rnd(), {A[i], i}, 1, Info(i - t[L].sz)); int x = create(now); apply(R, Tag(-1)); root = merge(L, merge(x, R)); }; auto erase = [&](int i) { auto [LL, R] = split_key(root, {A[i], i}); auto [L, trash] = split_sz(LL, t[LL].sz - 1); apply(R, Tag(1)); root = merge(L, R); }; for (int i = 0; i < n; ++i) { insert(i); } std::vector<int> answer(Q); for (int j = 0; j < Q; j++) { int i = X[j]; erase(i); A[i] = V[j]; insert(i); answer[j] = t[root].subtree.mx; } return answer; }

Compilation message (stderr)

bubblesort2.cpp: In constructor 'Node::Node(int, key_type, int, Info)':
bubblesort2.cpp:40:14: warning: 'Node::key' will be initialized after [-Wreorder]
   40 |     key_type key{};
      |              ^~~
bubblesort2.cpp:39:16: warning:   'int Node::sz' [-Wreorder]
   39 |     int y = 0, sz = 0;
      |                ^~
bubblesort2.cpp:48:5: warning:   when initialized here [-Wreorder]
   48 |     Node(int prior, key_type key, int siz, Info val) : y(prior), key(key), sz(siz), mine(val), subtree(val) {}
      |     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...