oj.uz

Submission #1019630

# Submission time Handle Problem Language Result Execution time Memory
1019630 2024-07-11T06:08:56 Z TAhmed33 Sličnost (COI23_slicnost) C++
17 / 100
 46 ms 43088 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mid ((l + r) >> 1)
const int MAXN = 1e6 + 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 <int, int> x, pair <int, int> 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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 3160 KB Output is correct
17 Correct 4 ms 3420 KB Output is correct
18 Correct 2 ms 1884 KB Output is correct
19 Correct 6 ms 3932 KB Output is correct
20 Correct 8 ms 5276 KB Output is correct
21 Correct 8 ms 5468 KB Output is correct
22 Correct 3 ms 2396 KB Output is correct
23 Correct 8 ms 4936 KB Output is correct
24 Correct 6 ms 5208 KB Output is correct
25 Correct 7 ms 4444 KB Output is correct
26 Correct 7 ms 5212 KB Output is correct
27 Correct 9 ms 5464 KB Output is correct
28 Correct 6 ms 4440 KB Output is correct
29 Correct 5 ms 3672 KB Output is correct
30 Correct 2 ms 1628 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 3160 KB Output is correct
17 Correct 4 ms 3420 KB Output is correct
18 Correct 2 ms 1884 KB Output is correct
19 Correct 6 ms 3932 KB Output is correct
20 Correct 8 ms 5276 KB Output is correct
21 Correct 8 ms 5468 KB Output is correct
22 Correct 3 ms 2396 KB Output is correct
23 Correct 8 ms 4936 KB Output is correct
24 Correct 6 ms 5208 KB Output is correct
25 Correct 7 ms 4444 KB Output is correct
26 Correct 7 ms 5212 KB Output is correct
27 Correct 9 ms 5464 KB Output is correct
28 Correct 6 ms 4440 KB Output is correct
29 Correct 5 ms 3672 KB Output is correct
30 Correct 2 ms 1628 KB Output is correct
31 Runtime error 46 ms 43088 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 3160 KB Output is correct
17 Correct 4 ms 3420 KB Output is correct
18 Correct 2 ms 1884 KB Output is correct
19 Correct 6 ms 3932 KB Output is correct
20 Correct 8 ms 5276 KB Output is correct
21 Correct 8 ms 5468 KB Output is correct
22 Correct 3 ms 2396 KB Output is correct
23 Correct 8 ms 4936 KB Output is correct
24 Correct 6 ms 5208 KB Output is correct
25 Correct 7 ms 4444 KB Output is correct
26 Correct 7 ms 5212 KB Output is correct
27 Correct 9 ms 5464 KB Output is correct
28 Correct 6 ms 4440 KB Output is correct
29 Correct 5 ms 3672 KB Output is correct
30 Correct 2 ms 1628 KB Output is correct
31 Incorrect 0 ms 348 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 3160 KB Output is correct
17 Correct 4 ms 3420 KB Output is correct
18 Correct 2 ms 1884 KB Output is correct
19 Correct 6 ms 3932 KB Output is correct
20 Correct 8 ms 5276 KB Output is correct
21 Correct 8 ms 5468 KB Output is correct
22 Correct 3 ms 2396 KB Output is correct
23 Correct 8 ms 4936 KB Output is correct
24 Correct 6 ms 5208 KB Output is correct
25 Correct 7 ms 4444 KB Output is correct
26 Correct 7 ms 5212 KB Output is correct
27 Correct 9 ms 5464 KB Output is correct
28 Correct 6 ms 4440 KB Output is correct
29 Correct 5 ms 3672 KB Output is correct
30 Correct 2 ms 1628 KB Output is correct
31 Runtime error 46 ms 43088 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -