oj.uz

Submission #804769

# Submission time Handle Problem Language Result Execution time Memory
804769 2023-08-03T11:13:26 Z myst6 Crossing (JOI21_crossing) C++14
49 / 100
 7000 ms 63312 KB 
#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

struct segtree2 {
    vector<int> nodes, upd;
    segtree2(int sz) {
        nodes.resize(sz*4);
        upd.resize(sz*4,-1);
    }
    segtree2() : segtree2(0) {}
    int lc(int x) { return x << 1; }
    int rc(int x) { return lc(x) | 1; }
    void pushdown(int x) {
        if (upd[x] != -1) {
            nodes[x] = upd[x];
            if (lc(x) < nodes.size()) nodes[lc(x)] = upd[x];
            if (rc(x) < nodes.size()) nodes[rc(x)] = upd[x];
            upd[x] = -1;
        }
    }
    void update(int l, int r, int x, int xl, int xr, bool b) {
        if (l > r) return;
        pushdown(x);
        if (l == xl && r == xr) {
            upd[x] = b;
        } else {
            int xm = (xl + xr) >> 1;
            update(l, min(r,xm), lc(x), xl, xm, b);
            update(max(xm+1,l), r, rc(x), xm+1, xr, b);
            pushdown(lc(x));
            pushdown(rc(x));
            nodes[x] = nodes[lc(x)] || nodes[rc(x)];
        }
    }
    bool query() {
        pushdown(1);
        return nodes[1];
    }
};

struct intervals {
    segtree2 tree;
    int sz;
    intervals(int sz) {
        this->sz = sz;
        tree = segtree2(sz);
    }
    intervals() : intervals(0) {}
    void add(int l, int r) {
        tree.update(l, r, 1, 0, sz-1, 1);
    }
    void remove(int l, int r) {
        tree.update(l, r, 1, 0, sz-1, 0);
    }
    bool empty() {
        return !tree.query();
    }
};

struct segtree {
    vector<char> orig;
    vector<char> upd;
    intervals wrong;
    segtree(string s) {
        int sz = (int)s.size();
        orig.resize(sz*4,0);
        upd.resize(sz*4,0);
        build(s,1,0,sz-1);
        wrong = intervals(sz);
    }
    int lc(int x) { return x << 1; }
    int rc(int x) { return lc(x) | 1; }
    void build(string &s, int x, int xl, int xr) {
        if (xl == xr) orig[x] = upd[x] = s[xl];
        else {
            int xm = (xl + xr) >> 1;
            build(s,lc(x),xl,xm);
            build(s,rc(x),xm+1,xr);
            if (orig[lc(x)] == orig[rc(x)]) {
                orig[x] = upd[x] = orig[lc(x)];
            }
        }
    }
    void check(int x, int xl, int xr) {
        if (upd[x] != orig[x]) {
            wrong.add(xl, xr);
        } else {
            wrong.remove(xl, xr);
        }
    }
    void pushdown(int x, int xl, int xr) {
        if (xl == xr) return;
        if (upd[x] == '0') return;
        wrong.remove(xl, xr);
        int xm = (xl + xr) >> 1;
        if (lc(x) < upd.size()) {
            upd[lc(x)] = upd[x];
            check(lc(x), xl, xm);
        }
        if (rc(x) < upd.size()) {
            upd[rc(x)] = upd[x];
            check(rc(x), xm+1, xr);
        }
        upd[x] = '0';
    }
    void update(int l, int r, int x, int xl, int xr, char c) {
        if (l > r) return;
        assert(x != 0);
        pushdown(x, xl, xr);
        if (l == xl && r == xr) {
            upd[x] = c;
            check(x, xl, xr);
        } else {
            int xm = (xl + xr) >> 1;
            update(l, min(xm,r), lc(x), xl, xm, c);
            update(max(xm+1,l), r, rc(x), xm+1, xr, c);
        }
    }
};

string cross(string a, string b) {
    string out = a;
    for (int i=0; i<(int)a.size(); i++) {
        if (a[i] != b[i]) {
            set<char> C = {'J', 'O', 'I'};
            C.erase(a[i]);
            C.erase(b[i]);
            out[i] = *C.begin();
        }
    }
    return out;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int n;
    cin >> n;
    string a, b, c;
    cin >> a >> b >> c;

    set<string> V;
    V.insert(a);
    V.insert(b);
    V.insert(c);
    bool upd = true;
    while (upd) {
        upd = false;
        for (auto it1=V.begin(); it1!=V.end(); it1++) {
            for (auto it2=V.begin(); it2!=V.end(); it2++) {
                if (it1 == it2) continue;
                string x = cross(*it1, *it2);
                if (!V.count(x)) {
                    V.insert(x);
                    upd = true;
                }
            }
        }
    }

    vector<segtree> trees;
    for (const string &s : V) {
        trees.push_back(segtree(s));
    }
    int q;
    cin >> q;
    string t;
    cin >> t;
    for (int i=0; i<(int)t.size(); i++) {
        for (segtree &tree : trees) tree.update(i,i,1,0,n-1,t[i]);
    }
    auto output_ans = [&]() {
        bool ans = false;
        for (segtree &tree : trees) {
            if (tree.wrong.empty()) {
                ans = true;
                break;
            }
        }
        cout << ( ans ? "Yes" : "No" ) << "\n";
    };
    output_ans();
    for (int i=0; i<q; i++) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        char c;
        cin >> c;
        for (segtree &tree : trees) tree.update(l,r,1,0,n-1,c);
        output_ans();
    }
    return 0;
}

Compilation message

Main.cpp: In member function 'void segtree2::pushdown(int)':
Main.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |             if (lc(x) < nodes.size()) nodes[lc(x)] = upd[x];
      |                 ~~~~~~^~~~~~~~~~~~~~
Main.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |             if (rc(x) < nodes.size()) nodes[rc(x)] = upd[x];
      |                 ~~~~~~^~~~~~~~~~~~~~
Main.cpp: In member function 'void segtree::pushdown(int, int, int)':
Main.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         if (lc(x) < upd.size()) {
      |             ~~~~~~^~~~~~~~~~~~
Main.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         if (rc(x) < upd.size()) {
      |             ~~~~~~^~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 2168 KB Output is correct
2 Correct 261 ms 2380 KB Output is correct
3 Correct 329 ms 2288 KB Output is correct
4 Correct 187 ms 2260 KB Output is correct
5 Correct 176 ms 2252 KB Output is correct
6 Correct 186 ms 2244 KB Output is correct
7 Correct 176 ms 2380 KB Output is correct
8 Correct 204 ms 2448 KB Output is correct
9 Correct 201 ms 2408 KB Output is correct
10 Correct 190 ms 2400 KB Output is correct
11 Correct 210 ms 2412 KB Output is correct
12 Correct 228 ms 2468 KB Output is correct
13 Correct 203 ms 2400 KB Output is correct
14 Correct 209 ms 2336 KB Output is correct
15 Correct 222 ms 2380 KB Output is correct
16 Correct 190 ms 2388 KB Output is correct
17 Correct 230 ms 2392 KB Output is correct
18 Correct 316 ms 2352 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 2168 KB Output is correct
2 Correct 261 ms 2380 KB Output is correct
3 Correct 329 ms 2288 KB Output is correct
4 Correct 187 ms 2260 KB Output is correct
5 Correct 176 ms 2252 KB Output is correct
6 Correct 186 ms 2244 KB Output is correct
7 Correct 176 ms 2380 KB Output is correct
8 Correct 204 ms 2448 KB Output is correct
9 Correct 201 ms 2408 KB Output is correct
10 Correct 190 ms 2400 KB Output is correct
11 Correct 210 ms 2412 KB Output is correct
12 Correct 228 ms 2468 KB Output is correct
13 Correct 203 ms 2400 KB Output is correct
14 Correct 209 ms 2336 KB Output is correct
15 Correct 222 ms 2380 KB Output is correct
16 Correct 190 ms 2388 KB Output is correct
17 Correct 230 ms 2392 KB Output is correct
18 Correct 316 ms 2352 KB Output is correct
19 Correct 2904 ms 13720 KB Output is correct
20 Correct 3239 ms 13548 KB Output is correct
21 Correct 909 ms 12716 KB Output is correct
22 Correct 1073 ms 11764 KB Output is correct
23 Correct 544 ms 3724 KB Output is correct
24 Correct 545 ms 3844 KB Output is correct
25 Correct 1057 ms 13612 KB Output is correct
26 Correct 1216 ms 13632 KB Output is correct
27 Correct 1949 ms 13696 KB Output is correct
28 Correct 1951 ms 13640 KB Output is correct
29 Correct 1841 ms 13264 KB Output is correct
30 Correct 852 ms 3728 KB Output is correct
31 Correct 1862 ms 13608 KB Output is correct
32 Correct 1891 ms 12488 KB Output is correct
33 Correct 692 ms 3696 KB Output is correct
34 Correct 2001 ms 13552 KB Output is correct
35 Correct 881 ms 10792 KB Output is correct
36 Correct 534 ms 3676 KB Output is correct
37 Correct 614 ms 3712 KB Output is correct
38 Correct 2915 ms 13492 KB Output is correct
39 Correct 459 ms 13680 KB Output is correct
40 Correct 908 ms 10048 KB Output is correct
41 Correct 3518 ms 13904 KB Output is correct
42 Correct 245 ms 13044 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 2168 KB Output is correct
2 Correct 261 ms 2380 KB Output is correct
3 Correct 329 ms 2288 KB Output is correct
4 Correct 187 ms 2260 KB Output is correct
5 Correct 176 ms 2252 KB Output is correct
6 Correct 186 ms 2244 KB Output is correct
7 Correct 176 ms 2380 KB Output is correct
8 Correct 204 ms 2448 KB Output is correct
9 Correct 201 ms 2408 KB Output is correct
10 Correct 190 ms 2400 KB Output is correct
11 Correct 210 ms 2412 KB Output is correct
12 Correct 228 ms 2468 KB Output is correct
13 Correct 203 ms 2400 KB Output is correct
14 Correct 209 ms 2336 KB Output is correct
15 Correct 222 ms 2380 KB Output is correct
16 Correct 190 ms 2388 KB Output is correct
17 Correct 230 ms 2392 KB Output is correct
18 Correct 316 ms 2352 KB Output is correct
19 Correct 1841 ms 2328 KB Output is correct
20 Correct 2783 ms 2292 KB Output is correct
21 Correct 487 ms 2380 KB Output is correct
22 Correct 407 ms 2124 KB Output is correct
23 Correct 495 ms 2428 KB Output is correct
24 Correct 506 ms 2368 KB Output is correct
25 Correct 496 ms 2384 KB Output is correct
26 Correct 424 ms 2396 KB Output is correct
27 Correct 502 ms 2400 KB Output is correct
28 Correct 438 ms 2212 KB Output is correct
29 Correct 507 ms 2448 KB Output is correct
30 Correct 427 ms 2184 KB Output is correct
31 Correct 1332 ms 2468 KB Output is correct
32 Correct 1268 ms 2332 KB Output is correct
33 Correct 1380 ms 2468 KB Output is correct
34 Correct 1138 ms 2228 KB Output is correct
35 Correct 1283 ms 2436 KB Output is correct
36 Correct 1323 ms 2468 KB Output is correct
37 Correct 1304 ms 2392 KB Output is correct
38 Correct 1249 ms 2476 KB Output is correct
39 Correct 1363 ms 2368 KB Output is correct
40 Correct 1263 ms 2440 KB Output is correct
41 Correct 1278 ms 2404 KB Output is correct
42 Correct 1353 ms 2456 KB Output is correct
43 Correct 1125 ms 2404 KB Output is correct
44 Correct 1265 ms 2396 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 2168 KB Output is correct
2 Correct 261 ms 2380 KB Output is correct
3 Correct 329 ms 2288 KB Output is correct
4 Correct 187 ms 2260 KB Output is correct
5 Correct 176 ms 2252 KB Output is correct
6 Correct 186 ms 2244 KB Output is correct
7 Correct 176 ms 2380 KB Output is correct
8 Correct 204 ms 2448 KB Output is correct
9 Correct 201 ms 2408 KB Output is correct
10 Correct 190 ms 2400 KB Output is correct
11 Correct 210 ms 2412 KB Output is correct
12 Correct 228 ms 2468 KB Output is correct
13 Correct 203 ms 2400 KB Output is correct
14 Correct 209 ms 2336 KB Output is correct
15 Correct 222 ms 2380 KB Output is correct
16 Correct 190 ms 2388 KB Output is correct
17 Correct 230 ms 2392 KB Output is correct
18 Correct 316 ms 2352 KB Output is correct
19 Correct 2904 ms 13720 KB Output is correct
20 Correct 3239 ms 13548 KB Output is correct
21 Correct 909 ms 12716 KB Output is correct
22 Correct 1073 ms 11764 KB Output is correct
23 Correct 544 ms 3724 KB Output is correct
24 Correct 545 ms 3844 KB Output is correct
25 Correct 1057 ms 13612 KB Output is correct
26 Correct 1216 ms 13632 KB Output is correct
27 Correct 1949 ms 13696 KB Output is correct
28 Correct 1951 ms 13640 KB Output is correct
29 Correct 1841 ms 13264 KB Output is correct
30 Correct 852 ms 3728 KB Output is correct
31 Correct 1862 ms 13608 KB Output is correct
32 Correct 1891 ms 12488 KB Output is correct
33 Correct 692 ms 3696 KB Output is correct
34 Correct 2001 ms 13552 KB Output is correct
35 Correct 881 ms 10792 KB Output is correct
36 Correct 534 ms 3676 KB Output is correct
37 Correct 614 ms 3712 KB Output is correct
38 Correct 2915 ms 13492 KB Output is correct
39 Correct 459 ms 13680 KB Output is correct
40 Correct 908 ms 10048 KB Output is correct
41 Correct 3518 ms 13904 KB Output is correct
42 Correct 245 ms 13044 KB Output is correct
43 Correct 1841 ms 2328 KB Output is correct
44 Correct 2783 ms 2292 KB Output is correct
45 Correct 487 ms 2380 KB Output is correct
46 Correct 407 ms 2124 KB Output is correct
47 Correct 495 ms 2428 KB Output is correct
48 Correct 506 ms 2368 KB Output is correct
49 Correct 496 ms 2384 KB Output is correct
50 Correct 424 ms 2396 KB Output is correct
51 Correct 502 ms 2400 KB Output is correct
52 Correct 438 ms 2212 KB Output is correct
53 Correct 507 ms 2448 KB Output is correct
54 Correct 427 ms 2184 KB Output is correct
55 Correct 1332 ms 2468 KB Output is correct
56 Correct 1268 ms 2332 KB Output is correct
57 Correct 1380 ms 2468 KB Output is correct
58 Correct 1138 ms 2228 KB Output is correct
59 Correct 1283 ms 2436 KB Output is correct
60 Correct 1323 ms 2468 KB Output is correct
61 Correct 1304 ms 2392 KB Output is correct
62 Correct 1249 ms 2476 KB Output is correct
63 Correct 1363 ms 2368 KB Output is correct
64 Correct 1263 ms 2440 KB Output is correct
65 Correct 1278 ms 2404 KB Output is correct
66 Correct 1353 ms 2456 KB Output is correct
67 Correct 1125 ms 2404 KB Output is correct
68 Correct 1265 ms 2396 KB Output is correct
69 Execution timed out 7049 ms 63312 KB Time limit exceeded
70 Halted 0 ms 0 KB -