Submission #1019632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019632		TAhmed33	Sličnost (COI23_slicnost)	C++98	50 / 100	331 ms	149584 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mid ((l + r) >> 1)
const int MAXN = 1e7 + 25;
int tl[MAXN], tr[MAXN];
pair <int, int> tree[MAXN];
int lazy[MAXN], cnt;
int new_leaf (int x) {
    cnt++; tree[cnt] = {0, 1};
    return cnt;
}
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};
}
int new_node (int l, int r) {
    cnt++;
    tree[cnt] = merge(tree[l], tree[r]);
    tl[cnt] = l; tr[cnt] = r;
    return cnt;
}
int build (int l, int r) {
    if (l == r) {
        return new_leaf(l);
    }
    return new_node(build(l, mid), build(mid + 1, r));
}
void prop (int l, int r, int node) {
    if (l != r) {
        lazy[tl[node]] += lazy[node];
        lazy[tr[node]] += lazy[node];
    }
    tree[node].first += lazy[node];
    lazy[node] = 0;
}
int update (int l, int r, int a, int b, int c, int node) {
    prop(l, r, node);
    if (l > b || r < a) return node;
    if (l >= a && r <= b) {
        if (l == r) {
            int x = new_leaf(l);
            tree[x] = tree[node];
            node = x;
        } else {
            prop(l, mid, tl[node]);
            prop(mid + 1, r, tr[node]);
            node = new_node(tl[node], tr[node]);
        }
        lazy[node] += c;
        prop(l, r, node);
        return node;
    }
    int x = update(l, mid, a, b, c, tl[node]);
    int y = update(mid + 1, r, a, b, c, tr[node]);
    return new_node(x, y);
}
pair <int, int> get (int l, int r, int a, int b, int node) {
    prop(l, r, node);
    if (l > b || r < a) return {-1, 0};
    if (l >= a && r <= b) return tree[node];
    return merge(get(l, mid, a, b, tl[node]), get(mid + 1, r, a, b, tr[node]));
}
int a[MAXN], n, k, q, p[MAXN];
int roots[MAXN];
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]];
    }
    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]);
    }
    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]);
    }
    for (int i = 1; i <= n - k + 1; i++) {
        auto g = get(1, n, 1, n, roots[i]);
        dd = merge(dd, get(1, n, 1, n, roots[i]));
    }
    cout << dd.first << " " << dd.second << '\n';
}       
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:89:14: warning: variable 'g' set but not used [-Wunused-but-set-variable]
   89 |         auto g = get(1, n, 1, n, roots[i]);
      |              ^

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