aboutsummaryrefslogtreecommitdiff
path: root/Semestr 4/aisd/pracownia4
diff options
context:
space:
mode:
authorFranciszek Malinka <franciszek.malinka@gmail.com>2021-04-08 15:00:33 +0200
committerFranciszek Malinka <franciszek.malinka@gmail.com>2021-04-08 15:00:33 +0200
commit2f83962f1799e94c8108c575d1c0d35868b06c4e (patch)
tree9ef3e16d3e80c8e44e93694e262199d8d5e6e7dc /Semestr 4/aisd/pracownia4
parentf64f7de412dd06affb0670831bdd117bde33a192 (diff)
Pracownia 4 aisd
Diffstat (limited to 'Semestr 4/aisd/pracownia4')
-rw-r--r--Semestr 4/aisd/pracownia4/brut.cpp69
-rw-r--r--Semestr 4/aisd/pracownia4/gen.py24
-rw-r--r--Semestr 4/aisd/pracownia4/rozw.cpp126
-rw-r--r--Semestr 4/aisd/pracownia4/rozw3.cpp149
-rwxr-xr-xSemestr 4/aisd/pracownia4/test.sh21
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