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 | 126 | ||||
| -rw-r--r-- | Semestr 4/aisd/pracownia4/rozw3.cpp | 149 | ||||
| -rwxr-xr-x | Semestr 4/aisd/pracownia4/test.sh | 21 |
5 files changed, 344 insertions, 45 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 index b3f97c8..9c314e2 100644 --- a/Semestr 4/aisd/pracownia4/rozw.cpp +++ b/Semestr 4/aisd/pracownia4/rozw.cpp @@ -1,8 +1,10 @@ #include <bits/stdc++.h> using namespace std; +typedef long long ll; -const int M = (1<<20); -const size_t size = M*2 + 10; +const int K = 20; +const int M = (1<<K); +const size_t tree_size = M*2 + 10; struct query { char type; @@ -16,14 +18,22 @@ struct query { int to; } sum; int del; - }; + } info; }; -struct segtreePS { - int tree[size]; +struct kox_set { + ll tree[tree_size]; - segtreePS() { - for (int i = 0; i < size; i++) tree[i] = 0; + 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) { @@ -34,10 +44,10 @@ struct segtreePS { } } - int query(int from, int to) { + ll sum(int from, int to) { from += M; to += M; - int ans = tree[from]; + ll ans = tree[from]; if (from != to) ans += tree[to]; while (from/2 != to/2) { if (from % 2 == 0) ans += tree[from + 1]; @@ -46,76 +56,102 @@ struct segtreePS { } return ans; } -}; - -struct segtreeSP { - int tree[size]; - - segtreeSP() { - for (int i = 0; i < size; i++) tree[i] = 0; - } - void update(int from, int to, int val) { - from += M; - to += M; - tree[from] += val; - if (from != val) tree[to] += val; - while (from/2 != to/2) { - if (from % 2 == 0) tree[from + 1] += val; - if (to % 2 == 1) tree[to - 1] += val; - to /= 2; from /= 2; + 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; } - int query(int where) { - int ans = 0; - where += M; - while (where) { - ans += tree[where]; - where /= 2; + 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]; + } } - return ans; } }; vector<query> queries; -segtreeSP sptree; 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; - scanf(" %c", &c); if (c == 'D') { int a; - cin >> a; - q.del = a; + scanf("%d", &a); + pstree.add(a); + q.info.del = a; } else { int a, b; - cin >> a >> b; + scanf("%d%d", &a, &b); q.type = c; if (c == 'I') { - q.insert = {a, b}; + q.info.insert = {a, b}; inserts++; } else { - q.sum = {a, b}; + q.info.sum = {a, b}; } } queries.push_back(q); } - for (int i = n-1; i > 0; i--) { + + secik.fill(1); + for (int i = n-1; i >= 0; i--) { query q = queries[i]; - if (q.type != 'I') continue; - int addition = sptree.query(q.insert.p); - q_to_pos[i] = addition + q.insert.p; + 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/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/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 |