Submission #1105520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105520		_callmelucian	Bliskost (COI23_bliskost)	C++14	100 / 100	748 ms	47832 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

int add (int a, int b) {
    assert(0 <= a && a < 26 && 0 <= b && b < 26);
    return a + b - (a + b < 26 ? 0 : 26);
}

int sub (int a, int b) {
    assert(0 <= a && a < 26 && 0 <= b && b < 26);
    return a - b + (a - b >= 0 ? 0 : 26);
}

int mul (int a, int b) {
    assert(0 <= a && a < 26 && 0 <= b && b < 26);
    return 1LL * a * b % 26;
}

struct IT {
    vector<pii> tr;
    IT (int sz) : tr(4 * sz) {}

    pii opr (pii a, pii b) {
        return {mul(a.first, b.first), add(mul(a.first, b.second), a.second)};
    }

    void update (int pos, pii val, int k, int l, int r) {
        if (pos < l || r < pos) return;
        if (l == r) return tr[k] = val, void();
        int mid = (l + r) >> 1;
        update(pos, val, 2 * k, l, mid);
        update(pos, val, 2 * k + 1, mid + 1, r);
        tr[k] = opr(tr[2 * k], tr[2 * k + 1]);
    }

    bool valid() { return tr[1].second == 0; }
};

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

    int n, q; cin >> n >> q;
    string s, t; cin >> s >> t;
    s = " " + s, t = " " + t;

    IT tree(n);
    for (int i = 1; i <= n; i++) {
        int val = sub(t[i] - 'a', s[i] - 'a');
        tree.update(i, make_pair(sub(0, 1), val), 1, 1, n);
    }

    cout << (tree.valid() ? "da" : "ne") << "\n";
    while (q--) {
        int p; char c; cin >> p >> c;
        int val = sub(t[p] - 'a', c - 'a');
        s[p] = c;
        tree.update(p, make_pair(sub(0, 1), val), 1, 1, n);
        cout << (tree.valid() ? "da" : "ne") << "\n";
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 17 / 17
• Subtask 6: 43 / 43