oj.uz

Submission #864220

# Submission time Handle Problem Language Result Execution time Memory
864220 2023-10-22T09:08:43 Z vjudge1 Crossing (JOI21_crossing) C++17
49 / 100
 7000 ms 61964 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define mp make_pair
struct seg2 {
    vi nodes, upd;
    seg2(int sz) {
        nodes.resize(sz*4);
        upd.resize(sz*4,-1);
    }
    seg2() : seg2(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 {
    seg2 tree;
    int sz;
    intervals(int sz) {
        this->sz = sz;
        tree = seg2(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 seg1 {
    vector<char> orig;
    vector<char> upd;
    intervals wrong;
    seg1(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]) {
            out[i] = 'J' + 'O' + 'I' - a[i] - b[i];
        }
    }
    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<seg1> trees;
    for (const string &s : V) {
        trees.push_back(seg1(s));
    }
    int q;
    cin >> q;
    string t;
    cin >> t;
    for (int i=0; i<(int)t.size(); i++) {
        for (seg1 &tree : trees) tree.update(i,i,1,0,n-1,t[i]);
    }
    auto output_ans = [&]() {
        bool ans = false;
        for (seg1 &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 (seg1 &tree : trees) tree.update(l,r,1,0,n-1,c);
        output_ans();
    }
    return 0;
}

Compilation message

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 848 KB Output is correct
2 Correct 271 ms 848 KB Output is correct
3 Correct 333 ms 1252 KB Output is correct
4 Correct 187 ms 852 KB Output is correct
5 Correct 176 ms 840 KB Output is correct
6 Correct 183 ms 848 KB Output is correct
7 Correct 174 ms 1052 KB Output is correct
8 Correct 205 ms 1304 KB Output is correct
9 Correct 197 ms 916 KB Output is correct
10 Correct 185 ms 852 KB Output is correct
11 Correct 192 ms 1152 KB Output is correct
12 Correct 212 ms 848 KB Output is correct
13 Correct 189 ms 848 KB Output is correct
14 Correct 191 ms 1032 KB Output is correct
15 Correct 190 ms 992 KB Output is correct
16 Correct 185 ms 964 KB Output is correct
17 Correct 198 ms 1264 KB Output is correct
18 Correct 307 ms 1040 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 848 KB Output is correct
2 Correct 271 ms 848 KB Output is correct
3 Correct 333 ms 1252 KB Output is correct
4 Correct 187 ms 852 KB Output is correct
5 Correct 176 ms 840 KB Output is correct
6 Correct 183 ms 848 KB Output is correct
7 Correct 174 ms 1052 KB Output is correct
8 Correct 205 ms 1304 KB Output is correct
9 Correct 197 ms 916 KB Output is correct
10 Correct 185 ms 852 KB Output is correct
11 Correct 192 ms 1152 KB Output is correct
12 Correct 212 ms 848 KB Output is correct
13 Correct 189 ms 848 KB Output is correct
14 Correct 191 ms 1032 KB Output is correct
15 Correct 190 ms 992 KB Output is correct
16 Correct 185 ms 964 KB Output is correct
17 Correct 198 ms 1264 KB Output is correct
18 Correct 307 ms 1040 KB Output is correct
19 Correct 2792 ms 10188 KB Output is correct
20 Correct 3184 ms 10080 KB Output is correct
21 Correct 937 ms 9412 KB Output is correct
22 Correct 1079 ms 8776 KB Output is correct
23 Correct 567 ms 1544 KB Output is correct
24 Correct 552 ms 1364 KB Output is correct
25 Correct 947 ms 10100 KB Output is correct
26 Correct 1156 ms 10248 KB Output is correct
27 Correct 1948 ms 10220 KB Output is correct
28 Correct 1947 ms 10316 KB Output is correct
29 Correct 1765 ms 10436 KB Output is correct
30 Correct 796 ms 1436 KB Output is correct
31 Correct 1751 ms 10248 KB Output is correct
32 Correct 1599 ms 9212 KB Output is correct
33 Correct 549 ms 1488 KB Output is correct
34 Correct 1682 ms 9932 KB Output is correct
35 Correct 783 ms 7704 KB Output is correct
36 Correct 496 ms 1468 KB Output is correct
37 Correct 498 ms 1360 KB Output is correct
38 Correct 2784 ms 10104 KB Output is correct
39 Correct 455 ms 10080 KB Output is correct
40 Correct 878 ms 6912 KB Output is correct
41 Correct 3348 ms 10468 KB Output is correct
42 Correct 221 ms 10296 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 848 KB Output is correct
2 Correct 271 ms 848 KB Output is correct
3 Correct 333 ms 1252 KB Output is correct
4 Correct 187 ms 852 KB Output is correct
5 Correct 176 ms 840 KB Output is correct
6 Correct 183 ms 848 KB Output is correct
7 Correct 174 ms 1052 KB Output is correct
8 Correct 205 ms 1304 KB Output is correct
9 Correct 197 ms 916 KB Output is correct
10 Correct 185 ms 852 KB Output is correct
11 Correct 192 ms 1152 KB Output is correct
12 Correct 212 ms 848 KB Output is correct
13 Correct 189 ms 848 KB Output is correct
14 Correct 191 ms 1032 KB Output is correct
15 Correct 190 ms 992 KB Output is correct
16 Correct 185 ms 964 KB Output is correct
17 Correct 198 ms 1264 KB Output is correct
18 Correct 307 ms 1040 KB Output is correct
19 Correct 1810 ms 1264 KB Output is correct
20 Correct 2831 ms 1036 KB Output is correct
21 Correct 511 ms 932 KB Output is correct
22 Correct 415 ms 876 KB Output is correct
23 Correct 508 ms 852 KB Output is correct
24 Correct 469 ms 840 KB Output is correct
25 Correct 530 ms 1408 KB Output is correct
26 Correct 415 ms 852 KB Output is correct
27 Correct 493 ms 1092 KB Output is correct
28 Correct 432 ms 876 KB Output is correct
29 Correct 504 ms 1024 KB Output is correct
30 Correct 399 ms 764 KB Output is correct
31 Correct 1257 ms 1216 KB Output is correct
32 Correct 1240 ms 1100 KB Output is correct
33 Correct 1253 ms 1152 KB Output is correct
34 Correct 1062 ms 1160 KB Output is correct
35 Correct 1256 ms 1020 KB Output is correct
36 Correct 1257 ms 1044 KB Output is correct
37 Correct 1273 ms 1248 KB Output is correct
38 Correct 1299 ms 1016 KB Output is correct
39 Correct 1357 ms 1184 KB Output is correct
40 Correct 1272 ms 868 KB Output is correct
41 Correct 1311 ms 1156 KB Output is correct
42 Correct 1314 ms 1140 KB Output is correct
43 Correct 1190 ms 944 KB Output is correct
44 Correct 1319 ms 1060 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 848 KB Output is correct
2 Correct 271 ms 848 KB Output is correct
3 Correct 333 ms 1252 KB Output is correct
4 Correct 187 ms 852 KB Output is correct
5 Correct 176 ms 840 KB Output is correct
6 Correct 183 ms 848 KB Output is correct
7 Correct 174 ms 1052 KB Output is correct
8 Correct 205 ms 1304 KB Output is correct
9 Correct 197 ms 916 KB Output is correct
10 Correct 185 ms 852 KB Output is correct
11 Correct 192 ms 1152 KB Output is correct
12 Correct 212 ms 848 KB Output is correct
13 Correct 189 ms 848 KB Output is correct
14 Correct 191 ms 1032 KB Output is correct
15 Correct 190 ms 992 KB Output is correct
16 Correct 185 ms 964 KB Output is correct
17 Correct 198 ms 1264 KB Output is correct
18 Correct 307 ms 1040 KB Output is correct
19 Correct 2792 ms 10188 KB Output is correct
20 Correct 3184 ms 10080 KB Output is correct
21 Correct 937 ms 9412 KB Output is correct
22 Correct 1079 ms 8776 KB Output is correct
23 Correct 567 ms 1544 KB Output is correct
24 Correct 552 ms 1364 KB Output is correct
25 Correct 947 ms 10100 KB Output is correct
26 Correct 1156 ms 10248 KB Output is correct
27 Correct 1948 ms 10220 KB Output is correct
28 Correct 1947 ms 10316 KB Output is correct
29 Correct 1765 ms 10436 KB Output is correct
30 Correct 796 ms 1436 KB Output is correct
31 Correct 1751 ms 10248 KB Output is correct
32 Correct 1599 ms 9212 KB Output is correct
33 Correct 549 ms 1488 KB Output is correct
34 Correct 1682 ms 9932 KB Output is correct
35 Correct 783 ms 7704 KB Output is correct
36 Correct 496 ms 1468 KB Output is correct
37 Correct 498 ms 1360 KB Output is correct
38 Correct 2784 ms 10104 KB Output is correct
39 Correct 455 ms 10080 KB Output is correct
40 Correct 878 ms 6912 KB Output is correct
41 Correct 3348 ms 10468 KB Output is correct
42 Correct 221 ms 10296 KB Output is correct
43 Correct 1810 ms 1264 KB Output is correct
44 Correct 2831 ms 1036 KB Output is correct
45 Correct 511 ms 932 KB Output is correct
46 Correct 415 ms 876 KB Output is correct
47 Correct 508 ms 852 KB Output is correct
48 Correct 469 ms 840 KB Output is correct
49 Correct 530 ms 1408 KB Output is correct
50 Correct 415 ms 852 KB Output is correct
51 Correct 493 ms 1092 KB Output is correct
52 Correct 432 ms 876 KB Output is correct
53 Correct 504 ms 1024 KB Output is correct
54 Correct 399 ms 764 KB Output is correct
55 Correct 1257 ms 1216 KB Output is correct
56 Correct 1240 ms 1100 KB Output is correct
57 Correct 1253 ms 1152 KB Output is correct
58 Correct 1062 ms 1160 KB Output is correct
59 Correct 1256 ms 1020 KB Output is correct
60 Correct 1257 ms 1044 KB Output is correct
61 Correct 1273 ms 1248 KB Output is correct
62 Correct 1299 ms 1016 KB Output is correct
63 Correct 1357 ms 1184 KB Output is correct
64 Correct 1272 ms 868 KB Output is correct
65 Correct 1311 ms 1156 KB Output is correct
66 Correct 1314 ms 1140 KB Output is correct
67 Correct 1190 ms 944 KB Output is correct
68 Correct 1319 ms 1060 KB Output is correct
69 Execution timed out 7034 ms 61964 KB Time limit exceeded
70 Halted 0 ms 0 KB -