oj.uz

Submission #911682

# Submission time Handle Problem Language Result Execution time Memory
911682 2024-01-19T04:38:10 Z The_Samurai Lamps (JOI19_lamps) C++17
0 / 100
 1000 ms 26868 KB 
// I stand with PALESTINE




//#pragma GCC optimize("Ofast,O3")
//#pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

template<typename T> struct SegTree {
    vector<T> tree;
    int size;
    T neutral_element = 1e9; // sum - 0, mx - (-INF), mn - INF

    inline T merge(T a, T b) {
        return min(a, b);
    }

    void init(int n) {
        size = 1;
        while (size <= n) size *= 2;
        tree.assign(2 * size, neutral_element);
    }

    void build(vector<T> &a) {
        size = 1;
        while (size < a.size()) size *= 2;
        tree.assign(2 * size, neutral_element);
        for (int i = size; i < size + a.size(); i++) tree[i] = a[i - size];
        for (int i = size - 1; i > 0; i--) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
    }

    void set(int p, T value) {  // set value at position p
        p += size;
        tree[p] = merge(value, tree[p]);
        for (; p > 1; p >>= 1) tree[p >> 1] = merge(tree[p], tree[p ^ 1]);
    }

    T get(int l, int r) {  // sum on interval [l, r]
        if (l > r) return neutral_element;
        T res = neutral_element;
        for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = merge(res, tree[l++]);
            if (r & 1) res = merge(res, tree[--r]);
        }
        return res;
    }
};


void solve() {
    int n;
    string s, t;
    cin >> n >> s >> t;
    s = "&" + s; t = "&" + t;
    vector<SegTree<int>> sg(2);
    for (int p = 0; p < 2; p++) {
        sg[p].init(n + 1);
        sg[p].set(0, 0);
        int l1 = 0, l2 = 0, eq = 0;
        for (int i = 1; i <= n; i++) {
            // teng emas
            if (s[i] != t[i]) l1++;
            else l1 = 0;
            if (l1) sg[p].set(i, sg[p].get(i - l1, i - l1) + 1);

            // hammasi teng
            if (s[i] == t[i]) eq++;
            else eq = 0;
            if (eq) sg[p].set(i, sg[p].get(i - eq, i - 1));

            // bir hil qib qo'yish
            if (t[i] == t[i - 1]) l2++;
            else l2 = 1;
            sg[p].set(i, sg[p].get(i - l2, i - l2) + 1);
        }
        for (int i = 1; i <= n; i++) s[i] ^= 1;
    }
    SegTree<int> ss; ss.init(n + 1);
    ss.set(0, 0);
    auto get = [&](int l, int r) -> int {
        int ans = sg[0].get(r, r) - sg[0].get(l - 1, l - 1);
        ans = min(ans, sg[1].get(r, r) - sg[1].get(l - 1, l - 1) + 1);
        return ans;
    };
    for (int i = 1; i <= n; i++) {
        int mn = 1e9;
        for (int j = i; j > 0; j--) {
            mn = min(mn, ss.get(j - 1, j - 1) + get(j, i));
        }
//        cout << i << ' ' << mn << endl;
        ss.set(i, mn);
    }
    cout << ss.get(n, n);
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int q = 1;
//    cin >> q;
    while (q--) {
        solve();
        cout << '\n';
    }
}

Subtask #1
0 / 6.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 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Incorrect 0 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.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 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Incorrect 0 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Execution timed out 1081 ms 26868 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.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 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Incorrect 0 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -