Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n, k;
- vector<int> a, tree;
- long long res;
- void update(int v, int tl, int tr, int pos, int x) {
- if (tl == tr) {
- tree[v] += x;
- } else {
- int tm = (tl + tr) / 2;
- if (pos <= tm) {
- update(v * 2, tl, tm, pos, x);
- } else {
- update(v * 2 + 1, tm + 1, tr, pos, x);
- }
- tree[v] = tree[v * 2] + tree[v * 2 + 1];
- }
- }
- int sum(int v, int tl, int tr, int l, int r) {
- if (l > r) {
- return 0;
- }
- if (tl == l && r == tr) {
- return tree[v];
- }
- int tm = (tl + tr) / 2;
- return sum(v * 2, tl, tm, l, min(r, tm)) + sum(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r);
- }
- int main() {
- ios_base::sync_with_stdio(NULL);
- cin.tie(0); cout.tie(0);
- cin >> n >> k;
- a.resize(n, 0);
- tree.resize(4 * n + 1, 0);
- while (k--) {
- for (int i = 0; i < n; ++i) {
- cin >> a[i];
- }
- for (int i = 0; i < tree.size(); ++i) {
- tree[i] = 0;
- }
- for (int i = 0; i < n; ++i) {
- res += sum(1, 1, n, a[i] + 1, n);
- update(1, 1, n, a[i], +1);
- }
- }
- cout << res;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
