oj.uz

Submission #680402

# Submission time Handle Problem Language Result Execution time Memory
680402 2023-01-10T17:37:06 Z bashkort Crossing (JOI21_crossing) C++17
26 / 100
 7000 ms 34332 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

string cross(string &a, string &b) {
    string res(a.size(), 'a');
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] == b[i]) {
            res[i] = a[i];
        } else {
            res[i] = 'J' ^ 'O' ^ 'I' ^ a[i] ^ b[i];
        }
    }
    return res;
}

constexpr int MOD[]{1000'000'000 + 7, 228228227, 998244353, 1000'000'000 + 9, 10696969};
constexpr int P = 239, hsz = size(MOD);

constexpr int N = 2e5 + 1;

struct Info {
    array<int, hsz> h{}, power{}, sum{};

    Info() = default;
};

vector<Info> t;
vector<int> tag;
int sz;

void apply(int x, int y) {
    if (y != -1) {
        for (int i = 0; i < hsz; ++i) {
            t[x].h[i] = 1LL * t[x].sum[i] * y % MOD[i];
        }
        tag[x] = y;
    }
}

void push(int x) {
    apply(x << 1, tag[x]);
    apply(x << 1 | 1, tag[x]);
    tag[x] = -1;
}

void pull(int x) {
    for (int i = 0; i < hsz; ++i) {
        t[x].h[i] = (t[x << 1].h[i] + 1LL * t[x << 1].power[i] * P % MOD[i] * t[x << 1 | 1].h[i]) % MOD[i];
        t[x].power[i] = 1LL * t[x << 1].power[i] * t[x << 1 | 1].power[i] % MOD[i] * P % MOD[i];
        t[x].sum[i] = (t[x << 1].sum[i] + 1LL * t[x << 1].power[i] * P % MOD[i] * t[x << 1 | 1].sum[i]) % MOD[i];
    }
}

int to_int(char c) {
    return c == 'J' ? 0 : 1 + (c == 'O');
}

void init(int n, string T) {
    sz = 1 << __lg(n) + bool(n & (n - 1));
    tag.assign(sz << 1, -1), t.resize(sz << 1);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < hsz; ++j) {
            t[i + sz].sum[j] = t[i + sz].power[j] = 1;
            t[i + sz].h[j] = to_int(T[i]);
        }
    }
    for (int i = sz - 1; i > 0; --i) {
        pull(i);
    }
}

void rangeApply(int l, int r, int tg, int x = 1, int lx = 0, int rx = sz) {
    if (l >= rx || lx >= r) {
        return;
    }
    if (l <= lx && rx <= r) {
        apply(x, tg);
        return;
    }

    push(x);

    int mid = (lx + rx) >> 1;

    rangeApply(l, r, tg, x << 1, lx, mid), rangeApply(l, r, tg, x << 1 | 1, mid, rx);

    pull(x);
}

array<int, hsz> hashed(string &s) {
    array<int, hsz> ans{};
    for (int i = int(s.size()) - 1; i >= 0; --i) {
        for (int j = 0; j < hsz; ++j) {
            ans[j] = (1LL * ans[j] * P + to_int(s[i])) % MOD[j];
        }
    }
    return ans;
}

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

    int n;
    cin >> n;

    string A, B, C;
    cin >> A >> B >> C;

    unordered_set<string> every{A, B, C};

    queue<string> qu;
    qu.push(A), qu.push(B), qu.push(C);

    while (!qu.empty()) {
        string s = qu.front();
        qu.pop();

        for (string to : every) {
            string res = cross(s, to);

            if (!every.count(res)) {
                qu.push(res);
                every.insert(res);
            }
        }
    }

    set<array<int, hsz>> st;
    for (string s : every) {
        st.insert(hashed(s));
    }

    int q;
    cin >> q;

    string T;
    cin >> T;

    init(n, T);

    cout << (st.count(t[1].h) ? "Yes\n" : "No\n");

    while (q--) {
        int l, r;
        char c;
        cin >> l >> r >> c;

        rangeApply(l - 1, r, to_int(c));
        for (int i = l - 1; i < r; ++i) {
            T[i] = c;
        }

//        assert(t[1].h == hashed(T));
        assert((hashed(T) == hashed(A)) == (A == T));
        cout << (st.count(t[1].h) ? "Yes\n" : "No\n");
    }

    return 0;
}

Compilation message

Main.cpp: In function 'std::string cross(std::string&, std::string&)':
Main.cpp:8:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for (int i = 0; i < a.size(); ++i) {
      |                     ~~^~~~~~~~~~
Main.cpp: In function 'void init(int, std::string)':
Main.cpp:61:23: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   61 |     sz = 1 << __lg(n) + bool(n & (n - 1));
      |               ~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1228 ms 960 KB Output is correct
2 Correct 1566 ms 904 KB Output is correct
3 Correct 1629 ms 852 KB Output is correct
4 Correct 1425 ms 876 KB Output is correct
5 Correct 1320 ms 2308 KB Output is correct
6 Correct 1381 ms 2308 KB Output is correct
7 Correct 1218 ms 2496 KB Output is correct
8 Correct 1579 ms 2452 KB Output is correct
9 Correct 1566 ms 2568 KB Output is correct
10 Correct 1618 ms 2364 KB Output is correct
11 Correct 1590 ms 2440 KB Output is correct
12 Correct 1641 ms 2456 KB Output is correct
13 Correct 1683 ms 2436 KB Output is correct
14 Correct 1634 ms 2156 KB Output is correct
15 Correct 1600 ms 800 KB Output is correct
16 Correct 1564 ms 972 KB Output is correct
17 Correct 1571 ms 888 KB Output is correct
18 Correct 1767 ms 936 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1228 ms 960 KB Output is correct
2 Correct 1566 ms 904 KB Output is correct
3 Correct 1629 ms 852 KB Output is correct
4 Correct 1425 ms 876 KB Output is correct
5 Correct 1320 ms 2308 KB Output is correct
6 Correct 1381 ms 2308 KB Output is correct
7 Correct 1218 ms 2496 KB Output is correct
8 Correct 1579 ms 2452 KB Output is correct
9 Correct 1566 ms 2568 KB Output is correct
10 Correct 1618 ms 2364 KB Output is correct
11 Correct 1590 ms 2440 KB Output is correct
12 Correct 1641 ms 2456 KB Output is correct
13 Correct 1683 ms 2436 KB Output is correct
14 Correct 1634 ms 2156 KB Output is correct
15 Correct 1600 ms 800 KB Output is correct
16 Correct 1564 ms 972 KB Output is correct
17 Correct 1571 ms 888 KB Output is correct
18 Correct 1767 ms 936 KB Output is correct
19 Execution timed out 7066 ms 34332 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1228 ms 960 KB Output is correct
2 Correct 1566 ms 904 KB Output is correct
3 Correct 1629 ms 852 KB Output is correct
4 Correct 1425 ms 876 KB Output is correct
5 Correct 1320 ms 2308 KB Output is correct
6 Correct 1381 ms 2308 KB Output is correct
7 Correct 1218 ms 2496 KB Output is correct
8 Correct 1579 ms 2452 KB Output is correct
9 Correct 1566 ms 2568 KB Output is correct
10 Correct 1618 ms 2364 KB Output is correct
11 Correct 1590 ms 2440 KB Output is correct
12 Correct 1641 ms 2456 KB Output is correct
13 Correct 1683 ms 2436 KB Output is correct
14 Correct 1634 ms 2156 KB Output is correct
15 Correct 1600 ms 800 KB Output is correct
16 Correct 1564 ms 972 KB Output is correct
17 Correct 1571 ms 888 KB Output is correct
18 Correct 1767 ms 936 KB Output is correct
19 Correct 2015 ms 2324 KB Output is correct
20 Correct 1834 ms 2324 KB Output is correct
21 Correct 1666 ms 2440 KB Output is correct
22 Correct 1183 ms 2184 KB Output is correct
23 Correct 2003 ms 2448 KB Output is correct
24 Correct 1520 ms 2360 KB Output is correct
25 Correct 1709 ms 2404 KB Output is correct
26 Correct 1746 ms 2284 KB Output is correct
27 Correct 1628 ms 2432 KB Output is correct
28 Correct 1368 ms 2220 KB Output is correct
29 Correct 1717 ms 2448 KB Output is correct
30 Correct 1158 ms 2212 KB Output is correct
31 Correct 1665 ms 2444 KB Output is correct
32 Correct 1528 ms 2344 KB Output is correct
33 Correct 1543 ms 2448 KB Output is correct
34 Correct 1197 ms 2304 KB Output is correct
35 Correct 1512 ms 2356 KB Output is correct
36 Correct 1549 ms 2280 KB Output is correct
37 Correct 1621 ms 896 KB Output is correct
38 Correct 1644 ms 884 KB Output is correct
39 Correct 1532 ms 972 KB Output is correct
40 Correct 1529 ms 932 KB Output is correct
41 Correct 1518 ms 832 KB Output is correct
42 Correct 1490 ms 848 KB Output is correct
43 Correct 1200 ms 928 KB Output is correct
44 Correct 1653 ms 864 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1228 ms 960 KB Output is correct
2 Correct 1566 ms 904 KB Output is correct
3 Correct 1629 ms 852 KB Output is correct
4 Correct 1425 ms 876 KB Output is correct
5 Correct 1320 ms 2308 KB Output is correct
6 Correct 1381 ms 2308 KB Output is correct
7 Correct 1218 ms 2496 KB Output is correct
8 Correct 1579 ms 2452 KB Output is correct
9 Correct 1566 ms 2568 KB Output is correct
10 Correct 1618 ms 2364 KB Output is correct
11 Correct 1590 ms 2440 KB Output is correct
12 Correct 1641 ms 2456 KB Output is correct
13 Correct 1683 ms 2436 KB Output is correct
14 Correct 1634 ms 2156 KB Output is correct
15 Correct 1600 ms 800 KB Output is correct
16 Correct 1564 ms 972 KB Output is correct
17 Correct 1571 ms 888 KB Output is correct
18 Correct 1767 ms 936 KB Output is correct
19 Execution timed out 7066 ms 34332 KB Time limit exceeded
20 Halted 0 ms 0 KB -