mamku ebal

TASK A
#include<bits/stdc++.h>
using namespace std;


string hsh(string s) {
	char start = s[0];
	for (char& ch : s) {
		ch -= start;
		if (ch < 0) ch += 26;
	}
	return s;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	string full;
	getline(cin, full);
	int pre = 0;
	map<string, string> mp;
	for (int i = 0; i <= full.size(); i++) {
		if (full[i] == ' ' || i == full.size()) {
			string current;
			for (int j = pre; j < i; j++) {
				current.push_back(full[j]);
			}
			if (current.size())
			mp[hsh(current)] = current;
			pre = i + 1;
		}
	}
	int q;
	string sq;
	getline(cin, sq);
	q = stoi(sq);
	while (q--) {
		string s;
		getline(cin, s);
		cout << mp[hsh(s)] << '\n';
	}
}
/////////////////////////////////

TASK B
#include<bits/stdc++.h>
#define all(x) begin(x),end(x)

using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	vector<pair<int,int>> arr(n);
	for (auto& [a, b] : arr) {
		cin >> a >> b;
		if (a > b) swap(a, b);
	}
	sort(all(arr));
	vector<int> mx(n);
	for (int i = n - 1; i >= 0; i--) {
		mx[i] = arr[i].second;
		if (i + 1 < n) {
			mx[i] = max(mx[i], mx[i + 1]);
		}
	}
	int lst = 0;
	int ans = 1;
	for (int i = n - 2; i >= 0; i--) {
		if (arr[i].first != arr[i + 1].first) {
			lst = max(lst, mx[i + 1]);
		}
		if (lst <= arr[i].second) {
			ans++;
		}
	}
	cout << ans << '\n';
}
////////////////////////

TASK C
#include<bits/stdc++.h>

#define endl "\n"
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

constexpr ld eps = 1e-9;

int n[2], c1 = INT32_MIN, c2 = INT32_MIN, le = INT32_MIN;
vector<tuple<int, int, bool>> vec[2], events;
vector<tuple<int, int, int>> coefs[2];
ld ans = 0;

ld t(ld x) {
  return x * x * x;
}

ld s(ld x) {
  return x * x;
}

ld func(ld a, ld b, ld c, ld l, ld r) {
  if (r - l < eps)
    return 0;
  return abs(a / 3 * (t(r) - t(l)) +
  b / 2 * (s(r) - s(l)) +
  c * (r - l));
}

ld get_ans(tuple<ld, ld, ld> a, tuple<ld, ld, ld> b, ld l, ld r) {
  auto [a1, b1, c1] = a;
  auto [a2, b2, c2] = b;
  a1 -= a2, b1 -= b2, c1 -= c2;
  if (abs(a1) < eps) {
    if (abs(b1) < eps) {
      return func(a1, b1, c1, l, r);
    }
    ld x1 = -c1 / b1;
    return
    func(0, b1, c1, l, min(x1, r)) +
    func(0, b1, c1, max(l, x1), r);
  }
  ld disc = b1 * b1 - a1 * c1 * 4;
  if (disc < eps) {
    return func(a1, b1, c1, l, r);
  }
  else {
    ld x1 = (-b1 - sqrtl(disc)) / (2 * a1);
    ld x2 = (-b1 + sqrtl(disc)) / (2 * a1);
    if (x1 > x2)
      swap(x1, x2);
    return
      func(a1, b1, c1, l, min(x1, r)) +
      func(a1, b1, c1, max(l, x1), min(x2, r)) +
      func(a1, b1, c1, max(l, x2), r);
  }
}

void Solve() {
  for (int i = 0; i < 2; i++)
    cin >> n[i];
  for (int i = 0; i < 2; i++) {
    for (int j = 0, v; j <= n[i]; j++) {
      cin >> v;
      vec[i].emplace_back(v, j, i);
    }
    for (int j = 0, a, b, c; j < n[i]; j++) {
      cin >> a >> b >> c;
      coefs[i].emplace_back(a, b, c);
    }
  }
  merge(vec[0].begin(), vec[0].end(),
  vec[1].begin(), vec[1].end(),
  back_inserter(events));
  for (auto [d, id, i]: events) {
    if (c1 != INT32_MIN && c2 != INT32_MIN && le != INT32_MIN) {
      ans += get_ans(coefs[0][c1], coefs[1][c2], le, d);
      le = d;
      if (i)
        c2 = id;
      else
        c1 = id;
    }
    else if (i) {
      le = d;
      c2 = id;
    }
    else {
      le = d;
      c1 = id;
    }
  }
  cout << fixed << setprecision(10) << ans;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  //auto start = chrono::high_resolution_clock::now();
  Solve();
  //auto end = chrono::high_resolution_clock::now();
  //cout << (chrono::duration_cast<chrono::duration<double>>(end - start)).count();
  return 0;
}
///////////////////////

TASK D
#pragma GCC Optimaze("Ofast")
#pragma GCC target("avx")

#include<bits/stdc++.h>
#define all(x) begin(x),end(x)

using namespace std;
using ll = long long;

const int mod = 1e9 + 7;

int dp[2][51][51][251];
const ll N = 1e5;

ll fact[N];
ll invfact[N];

ll fpow(ll a, ll p) {
	ll ans = 1;
	while (p) {
		if (p & 1) {
			ans = (ans * a) % mod;
		}
		a = (a * a) % mod;
		p >>= 1;
	}
	return ans;
}

ll rev(ll a) {
	return fpow(a, mod - 2);
}

void init() {
	fact[0] = 1;
	invfact[0] = 1;
	for (int i = 1; i < N; i++) {
		fact[i] = fact[i - 1] * i % mod;
		invfact[i] = rev(fact[i]);
	}
}

ll precalc[1000][1000];

ll C(int n, int m) {
	if (n < m) return 0;
	return precalc[n][m] = (fact[n] * invfact[m] % mod) * invfact[n - m] % mod;
}

ll C2(int n, int m) {
	if (n < m) return 0;
	return precalc[n][m];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	init();
	int n;

	for (int i = 0; i < 1000; i++) {
		for (int j = 0; j < 1000; j++) {
			precalc[i][j] = C(i, j);
		}
	}

	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(all(a));
	int cnt = accumulate(all(a), 0);
	dp[1][0][0][0] = 1;

	int sum = 0;

	for (int x = 0; x < n; x++) {
		int ni = x & 1;
		int pi = ni ^ 1;

		for (int cnt = 1; cnt < a[x]; cnt++) {
			for (int first_has = 0; first_has <= sum && first_has + cnt <= 250; first_has++) {
				ll coef = C2(first_has + cnt, cnt) * C2(sum - first_has + a[x] - cnt, a[x] - cnt) % mod;
				if (coef) {
#pragma GCC ivdep
					for (int i = 0; i <= x; i++) {
						for (int j = 0; j <= x; j++) {
							dp[ni][i + 1][j + 1][first_has + cnt] = (dp[ni][i + 1][j + 1][first_has + cnt] + dp[pi][i][j][first_has] * coef) % mod;
						}
					}
				}
			}
		}

		for (int first_has = 0; first_has <= 250; first_has++) {
			for (int i = 0; i <= x; i++) {
				for (int j = 0; j <= x; j++) {
					dp[ni][i + 1][j][first_has + a[x]] = (dp[ni][i + 1][j][first_has + a[x]] + dp[pi][i][j][first_has] * C2(first_has + a[x], a[x])) % mod;
					dp[ni][i][j + 1][first_has] = (dp[ni][i][j + 1][first_has] + dp[pi][i][j][first_has] * C2(sum - first_has + a[x], a[x])) % mod;
				}
			}
		}

		for (int i = 0; i <= 50; i++) {
			for (int j = 0; j <= 50; j++) {
				for (int k = 0; k <= 250; k++) {
					dp[pi][i][j][k] = 0;
				}
			}
		}

		sum += a[x];
	}

	ll ans = 0;

	for (int i = 0; i <= n; i++) {
		ans += dp[(n + 1) & 1][i][i][cnt / 2];
		ans %= mod;
	}
	ans *= rev(fact[cnt]);
	ans %= mod;
	for (int val : a) {
		ans = (ans * fact[val]) % mod;
	}
	cout << ans << '\n';
}
//////////////////////////////


TASK E
#include<bits/stdc++.h>

#define endl "\n"
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

constexpr int N = 3e5 + 5;

struct Treap {
  struct Node {
    int val;
    int sz;
    int pri;
    Node *l, *r;
    Node(int val = 0) :
    val(val), sz(1),
    pri(rand() ^ (rand() << 16)),
    l(nullptr), r(nullptr){};
  };

  using pN = Node*;
  using pNN = pair<pN, pN>;

  Node buff[N];
  int st = 0;
  pN root = nullptr;

  int getsz(pN v) {
    return v == nullptr ? 0: v -> sz;
  }

  int getval(pN v) {
    return v == nullptr ? 0 : v -> val;
  }

  pN newN(int v) {
    buff[st] = Node(v);
    return &buff[st++];
  }

  void recalc(pN v) {
    v -> sz = getsz(v -> l) + getsz(v -> r) + 1;
  }

  pN merge(pN l, pN r) {
    if (l == nullptr)
      return r;
    if (r == nullptr)
      return l;
    if (l -> pri < r -> pri) {
      l -> r = merge(l -> r, r);
      recalc(l);
      return l;
    }
    else {
      r -> l = merge(l, r -> l);
      recalc(r);
      return r;
    }
  }

  pNN split(pN v, int k) {
    if (k == 0)
      return {nullptr, v};
    if (getsz(v -> l) >= k) {
      auto p = split(v -> l, k);
      v -> l = p.second;
      recalc(v);
      return {p.first, v};
    }
    else {
      auto p = split(v -> r, k - getsz(v -> l) - 1);
      v -> r = p.first;
      recalc(v);
      return {v, p.second};
    }
  }

  void insert(int pos, int val) {
    auto p1 = split(root, pos - 1);
    auto v = newN(val);
    root = merge(p1.first, merge(v, p1.second));
    return;
  }

  void erase(int pos) {
    auto p1 = split(root, pos - 1);
    auto p2 = split(p1.second, 1);
    root = merge(p1.first, p2.second);
    return;
  }

  int get_ans(int pos) {
    auto p1 = split(root, pos - 1);
    auto p2 = split(p1.second, 1);
    int ans = getval(p2.first);
    root = merge(merge(p2.first, p1.first), p2.second);
    return ans;
  }
} tr;

struct SegTree {

  vector<int> tr;

  SegTree(int n) {
    tr.resize(n << 2);
  }

  void upd(int pos, int val, int i, int l, int r) {
    if (l + 1 == r) {
      tr[i] += val;
      return;
    }
    int mid = (l + r) >> 1;
    if (pos < mid)
      upd(pos, val, (i << 1) + 1, l, mid);
    else
      upd(pos, val, (i << 1) + 2, mid, r);
    tr[i] = (tr[(i << 1) + 1] + tr[(i << 1) + 2]);
  }

  int get(int l, int r, int i, int cl, int cr) {
    if (l >= r)
      return 0;
    if (l == cl && r == cr)
      return tr[i];
    int mid = (cl + cr) >> 1;
    return
    get(l, min(mid, r), (i << 1) + 1, cl, mid) +
    get(max(l, mid), r, (i << 1) + 2, mid, cr);
  }
};

int n, m, type;
vector<int> temp[N];
vector<int> vec, dop;

void Solve() {
  cin >> n >> m >> type;
  if (type == 2) {
    for (int i = 1; i <= m; i++)
      tr.insert(i, i);
    for (int i = 0, pos; i < n; i++) {
      cin >> pos;
      int a = tr.get_ans(pos);
      //assert(a > 0);
      cout << a << " ";
    }
  }
  else {
    for (int i = 0, v; i < n; i++) {
      cin >> v;
      vec.push_back(v);
    }
    dop = vec;
    reverse(dop.begin(), dop.end());
    for (int i = 1; i <= m; i++) {
      dop.push_back(i);
    }
    for (int i = 0; i < dop.size(); i++) {
      temp[dop[i]].push_back(i);
    }
    SegTree t(dop.size());
    for (int i = vec.size(); i < dop.size(); i++)
      t.upd(i, 1, 0, 0, dop.size());
    for (int i: vec) {
      int a = t.get(0, temp[i].back() + 1, 0, 0, dop.size());
      assert(a > 0);
      cout << a << ' ';
      t.upd(temp[i].back(), -1, 0, 0, dop.size());
      temp[i].pop_back();
      t.upd(temp[i].back(), 1, 0, 0, dop.size());
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  //auto start = chrono::high_resolution_clock::now();
  Solve();
  //auto end = chrono::high_resolution_clock::now();
  //cout << (chrono::duration_cast<chrono::duration<double>>(end - start)).count();
  return 0;
}
///////////////////////////////////

TASK F
#include<bits/stdc++.h>
#define all(x) begin(x),end(x)

using namespace std;
using ll = long long;

pair<ll, ll> getNum(string s) {
	ll a = 0, b = 0;
	for (int i = 0; i < int(s.size()); i++) {
		if (s[i] >= 'A' && s[i] <= 'Z') {
			a *= 26;
			a += s[i] - 'A' + 1;
		} else if (s[i] >= '0' && s[i] <= '9') {
			b *= 10;
			b += s[i] - '0';
		}
	}
	b--;
	a--;
	return {b, a};
}

void print(vector<string>& arr, int n, int m) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == ' ') {
				cout << ' ';
			} else {
				int h = (i > 0 ? arr[i - 1][j] != ' ' : 0) + (arr[i + 1][j] != ' ');
				int v = (j > 0 ? arr[i][j - 1] != ' ' : 0) + (arr[i][j + 1] != ' ');
				if (h > 0 && v > 0) {
					cout << '+';
				} else if (h > 0) {
					cout << '|';
				} else if (v > 0) {
					cout << '-';
				} else {
					assert(false);
				}
			}
		}
		cout << '\n';
	}
}

vector<string> split(string s) {
	vector<string> res;
	string cur = "";
	for (char ch : s) {
		if (ch != ' ') {
			cur.push_back(ch);
		} else {
			if (cur.size()) {
				res.push_back(cur);
			}
			cur = "";
		}
	}
	if (cur.size())  {
		res.push_back(cur);
	}
	return res;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	string nm;
	getline(cin, nm);
	vector<string> mn_arr = split(nm);
	int n = stoi(mn_arr[0]);
	int m = stoi(mn_arr[1]);

	vector<string> arr(n + 1);
	vector<string> brr(n + 1, string(m + 1, ' '));
	for (int i = 0; i < n; i++) {
		getline(cin, arr[i]);
		for (int j = 0; j < m; j++) {
			if (arr[i][j] != ' ') arr[i][j] = 'X';
			if (i == 0 || i + 1 == n || j == 0 || j + 1 == m) {
				brr[i][j] = 'X';
				arr[i][j] = 'X';
			}
		}
		arr[i].push_back(' ');
		arr[i][m] = ' ';
	}
	arr.back() = brr.back();

	string rows;
	getline(cin, rows);
	int row = stoi(rows);

	vector<int> h(row);
	string hs;
	getline(cin, hs);
	auto hsv = split(hs);
	for (int i = 0; i < row; i++) {
		h[i] = stoi(hsv[i]);
	}

	string cols;
	getline(cin, cols);
	int col = stoi(cols);

	vector<int> w(col);
	string ws;
	getline(cin, ws);
	auto wsv = split(ws);
	for (int i = 0; i < col; i++) {
		w[i] = stoi(wsv[i]);
	}

	{
		int cur = 0;
		for (int i = 0; i + 1 < row; i++) {
			cur += h[i] + 1;
			for (int j = 0; j < m; j++) {
				brr[cur][j] = 'X';
			}
		}
	}
	{
		int cur = 0;
		for (int i = 0; i + 1 < col; i++) {
			cur += w[i] + 1;
			for (int j = 0; j < n; j++) {
				brr[j][cur] = 'X';
			}
		}
	}

	vector<pair<int,int>> steps = {
		{0, 1},
		{1, 0},
		{0, -1},
		{-1, 0},
		{1, 1},
		{1, -1},
		{-1, 1},
		{-1, -1}
	};

	auto get_borders = [&] (int fx, int fy) {
		int mxx = fx, mxy = fy;
		int mnx = fx, mny = fy;

		vector<vector<bool>> used(n + 1, vector<bool>(m + 1, false));

		queue<pair<int,int>> q;
		q.emplace(fx, fy);
		while (q.size()) {
			auto [x, y] = q.front();

			mxx = max(mxx, x);
			mnx = min(mnx, x);

			mxy = max(mxy, y);
			mny = min(mny, y);
			q.pop();
			used[x][y] = true;
			for (auto& [dx, dy] : steps) {
				int nx = dx + x;
				int ny = dy + y;
				if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
				if (arr[nx][ny] != ' ') continue;
				if (used[nx][ny]) continue;
				used[nx][ny] = true;
				q.emplace(nx, ny);
			}
		}
		return pair<pair<int,int>, pair<int,int>> ({mnx - 1, mny - 1}, {mxx + 1, mxy + 1});
	};

	auto get_pos_by_cell = [&] (int x, int y) {
		int rx = 1;
		int ry = 1;
		for (int i = 0; i < x; i++) {
			rx += h[i] + 1;
		}
		for (int i = 0; i < y; i++) {
			ry += w[i] + 1;
		}
		return pair<int,int>(rx, ry);
	};


	string qs;
	getline(cin, qs);
	int q = stoi(qs);
	while (q--) {
		string inp;
		getline(cin, inp);
		auto vec = split(inp);

		string type = vec[0];
		if (type == "merge") {
			string a = vec[1], b = vec[2];
			auto [cx1, cy1] = getNum(a);
			auto [x1, y1] = get_pos_by_cell(cx1, cy1);
			auto [cx2, cy2] = getNum(b);
			auto [x2, y2] = get_pos_by_cell(cx2, cy2);

			auto [mn1, mx1] = get_borders(x1, y1);
			auto [mn2, mx2] = get_borders(x2, y2);

			if (mn1 == mn2 && mx1 == mx2) {
				cout << "Can not merge cell with itself\n";
			} else {
				if (mn1 > mn2) {
					swap(mn1, mn2);
					swap(mx1, mx2);
				}

				if (mn1.first == mn2.first
					&& mx1.first == mx2.first
					&& mx1.second == mn2.second) {
					cout << "Merged horizontally-aligned cells\n";
					for (int x = mn1.first + 1; x < mx2.first; x++) {
						for (int y = mn1.second + 1; y < mx2.second; y++) {
							arr[x][y] = ' ';
						}
					}
					print(arr, n, m);

				} else if (mn1.second == mn2.second
					&& mx1.second == mx2.second
					&& mx1.first == mn2.first) {
					cout << "Merged vertically-aligned cells\n";
					for (int x = mn1.first + 1; x < mx2.first; x++) {
						for (int y = mn1.second + 1; y < mx2.second; y++) {
							arr[x][y] = ' ';
						}
					}
					print(arr, n, m);
				} else {
					cout << "Can not merge unaligned cells\n";
				}
			}
 		} else {
			string a = vec[1];
			auto [cx1, cy1] = getNum(a);
			auto [x1, y1] = get_pos_by_cell(cx1, cy1);
			auto [mn, mx] = get_borders(x1, y1);
			bool good = false;
			for (int x = mn.first + 1; x < mx.first; x++) {
				for (int y = mn.second + 1; y < mx.second; y++) {
					if (arr[x][y] == ' ' && brr[x][y] != ' ') {
						good = true;
					}
					arr[x][y] = brr[x][y];
				}
			}

			if (good) {
				int hcnt = 0;
				int wcnt = 0;

				for (int y = mn.second; y < mx.second; y++) {
					if (arr[mn.first + 1][y] != ' ') {
						hcnt++;
					}
				}

				for (int x = mn.first; x < mx.first; x++) {
					if (arr[x][mn.second + 1] != ' ') {
						wcnt++;
					}
				}
				assert(wcnt < mx.first - mn.first);
				assert(hcnt < mx.second - mn.second);

				ll cnt = 1ll * hcnt * wcnt;
				assert(cnt > 1);
				cout << "Split onto " << cnt << " cells\n";
				print(arr, n, m);
			} else {
				cout << "Can not split elementary cell\n";
			}
		}
	}
}