Submission #1019793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019793		TAhmed33	Sličnost (COI23_slicnost)	C++98	100 / 100	1159 ms	428572 KiB

Main

        #include <bits/stdc++.h>
        using namespace std;
        typedef long long ll;
        pair <ll, ll> merge (pair <ll, ll> x, pair <ll, ll> y) {
            if (x.first > y.first) return x;
            if (x.first < y.first) return y;
            return {x.first, x.second + y.second};
        }
        #define mid ((l + r) >> 1)
        const int MAXN = 25'000'005;
        int tl[MAXN], tr[MAXN], sum[MAXN], cnt;
        pair <int, int> dp[MAXN];
        int new_leaf (int x) {
            cnt++; dp[cnt] = {0, 1};
            return cnt;
        }
        int new_node (int l, int r) {
            cnt++;
            dp[cnt] = merge(dp[l], dp[r]);
            tl[cnt] = l; tr[cnt] = r;
            return cnt;
        }
        int build (int l, int r) {
            if (l == r) {
                return new_leaf(l);
            } else {
                return new_node(build(l, mid), build(mid + 1, r));
            }
        }
        int update (int l, int r, int a, int b, int c, int node) {
            if (l > b || r < a) return node;
            if (l >= a && r <= b) {
                cnt++; if (cnt >= MAXN) assert(0); tl[cnt] = tl[node]; tr[cnt] = tr[node];
                sum[cnt] = sum[node]; dp[cnt] = dp[node];
                sum[cnt] += c; dp[cnt].first += c;
                return cnt;
            }
            int x = update(l, mid, a, b, c, tl[node]);
            int y = update(mid + 1, r, a, b, c, tr[node]);
            cnt++; if (cnt >= MAXN) assert(0);
            tl[cnt] = x; tr[cnt] = y;
            dp[cnt] = merge({dp[x].first + sum[node], dp[x].second}, {dp[y].first + sum[node], dp[y].second});
            sum[cnt] = sum[node];
            return cnt;
        }
        pair <ll, ll> get (int node) {
            return dp[node];
        }
        int a[100002], n, k, q, p[100002];
        int roots[100002];
        struct SegmentTree2 {
            pair <ll, ll> tree2[400001];
            void build (int l, int r, int node) {
                if (l == r) {
                    tree2[node] = {0, 1};
                } else {
                    build(l, mid, 2 * node);
                    build(mid + 1, r, 2 * node + 1);
                    tree2[node] = merge(tree2[2 * node], tree2[2 * node + 1]);
                }
            }
            void update (int l, int r, int a, pair <int, int> b, int node) {
                if (l > a || r < a) return;
                if (l == r) {
                    tree2[node] = b;
                    return;
                }
                update(l, mid, a, b, 2 * node);
                update(mid + 1, r, a, b, 2 * node + 1);
                tree2[node] = merge(tree2[2 * node], tree2[2 * node + 1]);
            }
        } cur;
        void val () {
            cout << cur.tree2[1].first << " " << cur.tree2[1].second << '\n';
        }
        void solve () {
            cin >> n >> k >> q;
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
            }
            for (int i = 1; i <= n; i++) {
                int x; cin >> x; p[x] = i;
            }
            for (int i = 1; i <= n; i++) {
                a[i] = p[a[i]];
            }
            cur.build(1, n - k + 1, 1);
            pair <ll, ll> dd = {-1, 0};
            roots[1] = build(1, n);
            for (int i = 1; i <= k; i++) {
                roots[1] = update(1, n, max(1, a[i] - k + 1), min(a[i], n - k + 1), 1, roots[1]);
            }
            cur.update(1, n - k + 1, 1, get(roots[1]), 1);
            for (int i = k + 1; i <= n; i++) {
                roots[i - k + 1] = roots[i - k];
                roots[i - k + 1] = update(1, n, max(1, a[i - k] - k + 1), min(a[i - k], n - k + 1), -1, roots[i - k + 1]);
                roots[i - k + 1] = update(1, n, max(1, a[i] - k + 1), min(a[i], n - k + 1), 1, roots[i - k + 1]);
                cur.update(1, n - k + 1, i - k + 1, get(roots[i - k + 1]), 1);
            }
            val();
            while (q--) {
                int t; cin >> t;
                if (t + 1 <= n - k + 1) {
                    roots[t + 1] = update(1, n, max(1, a[t + 1] - k + 1), min(a[t + 1], n - k + 1), -1, roots[t + 1]);
                    roots[t + 1] = update(1, n, max(1, a[t] - k + 1), min(a[t], n - k + 1), 1, roots[t + 1]);
                    cur.update(1, n - k + 1, t + 1, get(roots[t + 1]), 1);
                }
                if (t - k + 1 >= 1) {
                    roots[t - k + 1] = update(1, n, max(1, a[t + 1] - k + 1), min(a[t + 1], n - k + 1), 1, roots[t - k + 1]);
                    roots[t - k + 1] = update(1, n, max(1, a[t] - k + 1), min(a[t], n - k + 1), -1, roots[t - k + 1]);
                    cur.update(1, n - k + 1, t - k + 1, get(roots[t - k + 1]), 1);
                }
                swap(a[t], a[t + 1]);
                val();
            }
        }       
        signed main () {
         
            ios::sync_with_stdio(0); cin.tie(0);
            int tc = 1; //cin >> tc;
            while (tc--) solve();
        }

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:88:27: warning: variable 'dd' set but not used [-Wunused-but-set-variable]
   88 |             pair <ll, ll> dd = {-1, 0};
      |                           ^~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 33 / 33
• Subtask 4: 7 / 7
• Subtask 5: 10 / 10
• Subtask 6: 33 / 33