Submission #1362723

#TimeUsernameProblemLanguageResultExecution timeMemory
1362723anteknneLamps (JOI19_lamps)C++20
4 / 100
290 ms26164 KiB
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 1000 * 1000 + 17;
string a, b;
int dp[MAXN][4];
int st[MAXN * 4];

void aktualizuj(int p, int k, int ind, ll w, int i) {
    if (p == k && p == ind) {
        st[i] = w;
        return;
    }
    int sr = (p + k) / 2;
    if (ind <= sr) {
        aktualizuj(p, sr, ind, w, i * 2);
    } else {
        aktualizuj(sr + 1, k, ind, w, i * 2 + 1);
    }
    st[i] = min(st[i * 2], st[i * 2 + 1]);
}

int zapytanie(int p, int k, int a, int b, int i) {
    if (p > b || k < a) {
        return MAXN;
    }
    if (a <= p && k <= b) {
        return st[i];
    }
    int sr = (p + k) / 2;
    return min(zapytanie(p, sr, a, b, i * 2), zapytanie(sr + 1, k, a, b, i * 2 + 1));
}

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin >> n >> a >> b;

    a = "#" + a;
    b = "#" + b;
    for (int i = 1; i <= n; i ++) {
        if (b[i] == '1') {
            dp[i][1] = dp[i - 1][1] + 1;
        }
        if (b[i] == '0') {
            dp[i][0] = dp[i - 1][0] + 1;
        }
        if (a[i] == b[i]) {
            dp[i][2] = dp[i - 1][2] + 1;
        }
        if (a[i] != b[i]) {
            dp[i][3] = dp[i - 1][3] + 1;
        }
    }

    for (int i = 1; i <= n; i ++) {
        int x = MAXN;
        if (dp[i][0] != 0) {
            x = min(x, zapytanie(0, n, i - dp[i][0], i - 1, 1) + 1);
        }
        if (dp[i][1] != 0) {
            x = min(x, zapytanie(0, n, i - dp[i][1], i - 1, 1) + 1);
        }
        if (dp[i][2] != 0) {
            x = min(x, zapytanie(0, n, i - dp[i][2], i - 1, 1));
        }
        if (dp[i][3] != 0) {
            x = min(x, zapytanie(0, n, i - dp[i][3], i - 1, 1) + 1);
        }
        aktualizuj(0, n, i, x, 1);
    }

    cout << zapytanie(0, n, n, n, 1) << "\n";


    return 0;
}


#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...