Submission #1019784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019784		TAhmed33	Sličnost (COI23_slicnost)	C++98	67 / 100	1459 ms	524288 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)
int cnt;
vector <int> tl = {0}, tr = {0}, sum = {0};
vector <pair <ll, ll>> dp = {{0, 0}};
int new_leaf (int x) {
    cnt++; 
    dp.push_back({0, 1});
    tl.push_back(0); tr.push_back(0); sum.push_back(0);
    return cnt;
}
int new_node (int l, int r) {
    cnt++;
    dp.push_back(merge(dp[l], dp[r]));
    tl.push_back(l); tr.push_back(r);
    sum.push_back(0);
    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++;  tl.push_back(tl[node]); tr.push_back(tr[node]);
        sum.push_back(sum[node]); dp.push_back(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++; 
    tl.push_back(x); tr.push_back(y);
    dp.push_back(merge({dp[x].first + sum[node], dp[x].second}, {dp[y].first + sum[node], dp[y].second}));
    sum.push_back(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[4000001];
    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:91:19: warning: variable 'dd' set but not used [-Wunused-but-set-variable]
   91 |     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: 0 / 33