diff options
Diffstat (limited to 'semestr-4/aisd/pracownia4')
| -rw-r--r-- | semestr-4/aisd/pracownia4/brut.cpp | 69 | ||||
| -rw-r--r-- | semestr-4/aisd/pracownia4/gen.py | 24 | ||||
| -rw-r--r-- | semestr-4/aisd/pracownia4/rozw.cpp | 157 | ||||
| -rw-r--r-- | semestr-4/aisd/pracownia4/rozw2.cpp | 135 | ||||
| -rw-r--r-- | semestr-4/aisd/pracownia4/rozw3.cpp | 149 | ||||
| -rw-r--r-- | semestr-4/aisd/pracownia4/show_problem.pdf | bin | 0 -> 61345 bytes | |||
| -rwxr-xr-x | semestr-4/aisd/pracownia4/test.sh | 21 |
7 files changed, 555 insertions, 0 deletions
diff --git a/semestr-4/aisd/pracownia4/brut.cpp b/semestr-4/aisd/pracownia4/brut.cpp new file mode 100644 index 0000000..32f4ebb --- /dev/null +++ b/semestr-4/aisd/pracownia4/brut.cpp @@ -0,0 +1,69 @@ +#include <bits/stdc++.h> +using namespace std; +typedef long long ll; + +struct insert_list { + vector<int> v; + + insert_list() { + } + + void insert(int p, int val) { + assert(p <= v.size()); + assert(p >= 0); + vector<int> temp; + for (int i = 0; i < p; i++) { + temp.push_back(v[i]); + } + temp.push_back(val); + for (int i = p; i < v.size(); i++) { + temp.push_back(v[i]); + } + v = temp; + } + + void erase(int p) { + assert(p <= v.size()); + assert(p >= 1); + vector<int> temp; + for (int i = 0; i < p-1; i++) { + temp.push_back(v[i]); + } + for (int i = p; i < v.size(); i++) { + temp.push_back(v[i]); + } + v = temp; + } + + ll sum(int l, int r) { + ll ans = 0; + for (int i = l-1; i < r; i++) { + ans += v[i]; + } + return ans; + } +}; + +insert_list v; + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(); + int n; + cin >> n; + for (int i = 0; i < n; i++) { + char c; + cin >> c; + if (c == 'D') { + int a; + cin >> a; + v.erase(a); + } + else { + int a, b; + cin >> a >> b; + if (c == 'I') v.insert(a, b); + else cout << v.sum(a,b) << "\n"; + } + } +}
\ No newline at end of file diff --git a/semestr-4/aisd/pracownia4/gen.py b/semestr-4/aisd/pracownia4/gen.py new file mode 100644 index 0000000..733a60e --- /dev/null +++ b/semestr-4/aisd/pracownia4/gen.py @@ -0,0 +1,24 @@ +from random import randint, seed, choice +import sys + + +seed(sys.argv[1]) +n = int(sys.argv[2]) +l = 0 +print(n) + + +for i in range(n): + c = choice('ISD') + if l == 0: + c = 'I' + + if c == 'D': + print(c, randint(1, l)) + l -= 1 + elif c == 'I': + print(c, randint(0, l), randint(-10, 10)) + l += 1 + else: + a = randint(1, l) + print(c, a, randint(a, l))
\ No newline at end of file diff --git a/semestr-4/aisd/pracownia4/rozw.cpp b/semestr-4/aisd/pracownia4/rozw.cpp new file mode 100644 index 0000000..9c314e2 --- /dev/null +++ b/semestr-4/aisd/pracownia4/rozw.cpp @@ -0,0 +1,157 @@ +#include <bits/stdc++.h> +using namespace std; +typedef long long ll; + +const int K = 20; +const int M = (1<<K); +const size_t tree_size = M*2 + 10; + +struct query { + char type; + union { + struct insert { + int p; + int x; + } insert; + struct sum { + int from; + int to; + } sum; + int del; + } info; +}; + +struct kox_set { + ll tree[tree_size]; + + kox_set() { + for (int i = 0; i < tree_size; i++) tree[i] = 0; + } + + void add(int val) { + update(val, 1); + } + + void del(int val) { + update(val, -1); + } + + void update(int where, int val) { + where += M; + while (where) { + tree[where] += val; + where /= 2; + } + } + + ll sum(int from, int to) { + from += M; + to += M; + ll ans = tree[from]; + if (from != to) ans += tree[to]; + while (from/2 != to/2) { + if (from % 2 == 0) ans += tree[from + 1]; + if (to % 2 == 1) ans += tree[to - 1]; + to /= 2; from /= 2; + } + return ans; + } + + int kth_elem(int k) { + int where = 1; + while (where < M) { + where *= 2; + if (tree[where] < k) { + k -= tree[where]; + where += 1; + } + } + return where - M; + } + + void fill(int value) { + for (int i = 0; i < M; i++) { + tree[i + M] = value; + } + for (int d = K-1; d >= 0; d--) { + int maks = (1<<d); + for (int i = 0; i < maks; i++) { + int ind = i + maks; + tree[ind] = tree[ind*2] + tree[ind*2 + 1]; + } + } + } +}; + +vector<query> queries; +map<int, int> q_to_pos; +kox_set secik; +kox_set pstree; + + +int main() { + int n, inserts = 0; + scanf("%d", &n); + for (int i = 0; i < n; ++i) { + char c; + scanf(" %c", &c); + query q; + q.type = c; + if (c == 'D') { + int a; + scanf("%d", &a); + pstree.add(a); + q.info.del = a; + } + else { + int a, b; + scanf("%d%d", &a, &b); + q.type = c; + if (c == 'I') { + q.info.insert = {a, b}; + inserts++; + } else { + q.info.sum = {a, b}; + } + } + queries.push_back(q); + } + + secik.fill(1); + for (int i = n-1; i >= 0; i--) { + query q = queries[i]; + if (q.type == 'D') { + pstree.del(q.info.del); + } + if (q.type == 'I') { + int offset = pstree.sum(0, q.info.insert.p); + int kth = secik.kth_elem(q.info.insert.p + offset + 1); + secik.del(kth); + q_to_pos[i] = kth; + cout << q.info.insert.p << " " << offset << "\n"; + cout << i << ": " << q_to_pos[i] << "\n"; + } + } + secik.fill(0); + pstree.fill(0); + + for (int i = 0; i < n; i++) { + query q = queries[i]; + if (q.type == 'I') { + secik.add(q_to_pos[i]); + pstree.update(q_to_pos[i], q.info.insert.x); + // cout << "Inserting " << q.info.insert.x << " to " << q_to_pos[i] << "\n"; + } + if (q.type == 'D') { + int pos = secik.kth_elem(q.info.del); + // cout << "kth: " << q.info.del << " " << pos << "\n"; + secik.del(pos); + pstree.update(pos, -pstree.tree[pos + M]); + } + if (q.type == 'S') { + int from = secik.kth_elem(q.info.sum.from); + int to = secik.kth_elem(q.info.sum.to); + printf("%lld\n", pstree.sum(from, to)); + } + } +}
\ No newline at end of file diff --git a/semestr-4/aisd/pracownia4/rozw2.cpp b/semestr-4/aisd/pracownia4/rozw2.cpp new file mode 100644 index 0000000..17562a9 --- /dev/null +++ b/semestr-4/aisd/pracownia4/rozw2.cpp @@ -0,0 +1,135 @@ +#include <bits/stdc++.h> +using namespace std; + +struct treap { + typedef long long T; + treap *left = nullptr; + treap *right = nullptr; + int rank, items = 1; + T value; + T sum; + bool rev = false; + + treap(T val = T()) : rank(rand()), value(val), sum(val) {} + + inline void update() { + if (rev) { + swap(left, right); + if (left) left->rev = !left->rev; + if (right) right->rev = !right->rev; + rev = false; + } + } +}; + +inline int items(treap *t) { return t ? t->items : 0; } +inline int sum(treap *t) { return t ? t->sum : 0; } +inline void recalc(treap *t) { + t->items = items(t->left) + items(t->right) + 1; + t->sum = sum(t->left) + sum(t->right) + t->value; +} + +pair<treap*, treap*> split(treap *t, int k) { + if (!t) return {nullptr, nullptr}; + t->update(); + if (items(t->left) < k) { + auto p = split(t->right, k - items(t->left) - 1); + t->right = p.first; + recalc(t); + return {t, p.second}; + } + else { + auto p = split(t->left, k); + t->right = p.first; + recalc(t); + return {p.first, t}; + } +} + +treap* merge(treap *a, treap *b) { + if (!a) return b; + if (!b) return a; + a->update(); + b->update(); + if (a->rank > b->rank) { + a->right = merge(a->right, b); + recalc(a); + return a; + } + else { + b->left = merge(a, b->left); + recalc(b); + return b; + } +} + +treap::T select(treap *t, int k) { + if (!t) return treap::T(); + t->update(); + int i = items(t->left); + if (i == k) return t->value; + else if (i > k) return select(t->left, k); + else return select(t->right, k - i - 1); +} + +treap *insert (treap *t, treap::T val, int k) { + auto p = split(t, k); + return merge(merge(p.first, new treap(val)), p.second); +} + +treap *erase(treap *t, int k) { + auto p1 = split(t, k); + auto p2 = split(p1.second, 1); + return merge(p1.first, p2.second); +} + +treap::T sum(treap *t, int l, int r) { + auto p1 = split(t, r); + auto p2 = split(p1.first, l); + return sum(p2.second); +} + +void write(treap *t) { + if (!t) return; + t->update(); + write(t->left); + cout << t->value << " "; + write(t->right); +} +void destroy(treap *t) { + if (!t) return; + destroy(t->left); + destroy(t->right); + delete t; +} + +treap *t = 0; + +int main() { + int n; + scanf("%d", &n); + for (int i = 0; i < n; i++) { + char c; + scanf(" %c", &c); + if (c == 'I') { + int p, x; + scanf("%d%d", &p, &x); + t = insert(t, x, p); + } + if (c == 'D') { + int p; + scanf("%d", &p); + t = erase(t, p - 1); + } + if (c == 'S') { + int l, r; + scanf("%d%d", &l, &r); + printf("ans: %lld\n", sum(t, l, r)); + } + cout << "Treap:\n"; + write(t); + cout << "\n"; + } + + destroy(t); +}
\ No newline at end of file diff --git a/semestr-4/aisd/pracownia4/rozw3.cpp b/semestr-4/aisd/pracownia4/rozw3.cpp new file mode 100644 index 0000000..ec107ef --- /dev/null +++ b/semestr-4/aisd/pracownia4/rozw3.cpp @@ -0,0 +1,149 @@ + +#include <bits/stdc++.h> +using namespace std; + +struct treap +{ + typedef long long T; + treap *left = nullptr, *right = nullptr; + + int rank, items = 1; + bool rev = false; + T value, sum; + + treap(T val = T()) : value(val), sum(val), rank(rand()) { } + + inline void update() + { + if(rev) + { + swap(left, right); + if(left) left->rev = !left->rev; + if(right) right->rev = !right->rev; + rev = false; + } + } +}; + +inline int items(treap *t) { return t ? t->items : 0; } +inline treap::T sum(treap *t) { return t ? t->sum : 0; } +inline void recalc(treap *t) { + t->items = items(t->left) + items(t->right) + 1; + t->sum = sum(t->left) + sum(t->right) + t->value; +} + +pair<treap*, treap*> split(treap *t, int k) //dzieli na prefiks dlugosci k i reszte +{ + if(!t) return make_pair(nullptr, nullptr); + //t = new treap(*t); //odkomentowac zeby zrobic strukture trwala + t->update(); + if(items(t->left) < k) + { + auto p = split(t->right, k - items(t->left) - 1); + t->right = p.first; + recalc(t); + return make_pair(t, p.second); + } + else + { + auto p = split(t->left, k); + t->left = p.second; + recalc(t); + return make_pair(p.first, t); + } +} + +treap* merge(treap *a, treap *b) +{ + if(!a) return b; + if(!b) return a; + a->update(); + b->update(); + if(a->rank > b->rank) { + a->right = merge(a->right, b); + recalc(a); + return a; + } + else { + b->left = merge(a, b->left); + recalc(b); + return b; + } +} + +treap::T select(treap *t, int k) //zwraca k-ty element +{ + if(!t) return treap::T(); + t->update(); + int i = items(t->left); + if(i == k) return t->value; + if(i > k) return select(t->left, k); + return select(t->right, k - i - 1); +} + +treap* insert(treap *t, treap::T val, int k) //wstaw val na pozycje k (liczac od 0) +{ + auto p = split(t, k); + return merge(merge(p.first, new treap(val)), p.second); +} +void write(treap *t) +{ + if(!t) return; + t->update(); + write(t->left); + cout << "(" << t->value << ", " << t->sum << ") "; + write(t->right); +} + +treap* erase(treap *t, int k) +{ + auto p1 = split(t, k); + auto p2 = split(p1.second, 1); + return merge(p1.first, p2.second); +} + +treap* reverse(treap *t, int a, int b) //odwroc przedzial <a, b) +{ + auto p1 = split(t, b); + auto p2 = split(p1.first, a); + if(p2.second) p2.second->rev = !p2.second->rev; + return merge(merge(p2.first, p2.second), p1.second); +} + +treap::T sum(treap* t, int l, int r) { + auto p1 = split(t, r); + auto p2 = split(p1.first, l); + treap::T ret = sum(p2.second); + merge(merge(p2.first, p2.second), p1.second); + return ret; +} + +treap *root = 0; + +int main() { + int n; + scanf("%d", &n); + for (int i = 0; i < n; i++) { + char c; + scanf(" %c", &c); + if (c == 'I') { + int p, x; + scanf("%d%d", &p, &x); + root = insert(root, x, p); + } + if (c == 'D') { + int p; + scanf("%d", &p); + root = erase(root, p - 1); + } + if (c == 'S') { + int l, r; + scanf("%d%d", &l, &r); + printf("%lld\n", sum(root, l - 1, r)); + } + // cout << "Treap:\n"; + // write(root); + // cout << "\n"; + } + +}
\ No newline at end of file diff --git a/semestr-4/aisd/pracownia4/show_problem.pdf b/semestr-4/aisd/pracownia4/show_problem.pdf Binary files differnew file mode 100644 index 0000000..8a1c155 --- /dev/null +++ b/semestr-4/aisd/pracownia4/show_problem.pdf diff --git a/semestr-4/aisd/pracownia4/test.sh b/semestr-4/aisd/pracownia4/test.sh new file mode 100755 index 0000000..dc725ad --- /dev/null +++ b/semestr-4/aisd/pracownia4/test.sh @@ -0,0 +1,21 @@ +#!/bin/bash + +make brut +make rozw3 + + +for i in {1..10000} +do + echo $i + python3 gen.py $i $1 > test.in + ./rozw3 < test.in > wa.out + ./brut < test.in > test.out + + if diff -w test.out wa.out + then + echo ok + else + echo nieok + break + fi +done |