oj.uz

Submission #870015

# Submission time Handle Problem Language Result Execution time Memory
870015 2023-11-06T16:00:54 Z NeroZein Crossing (JOI21_crossing) C++17
100 / 100
 1913 ms 119588 KB 
    #include "bits/stdc++.h"
    using namespace std;
     
    #ifdef Nero
    #include "Deb.h"
    #else
    #define deb(...)
    #endif
     
    const int V = 30; 
    const int N = 2e5 + 5; 
     
    int cnt = 3; 
    int a[V][N]; 
    int lazy[N * 2]; 
    int ch[V][N * 2], seg[V][N * 2];
     
    void build(int ver, int nd, int l, int r) {
      if (l == r) {
        ch[ver][nd] = a[ver][l];
        seg[ver][nd] = ch[ver][nd] == ch[cnt][nd]; 
        return;
      }
      int mid = (l + r) >> 1;
      int rs = nd + ((mid - l + 1) << 1);
      build(ver, nd + 1, l, mid);
      build(ver, rs, mid + 1, r);
      seg[ver][nd] = (seg[ver][nd + 1] & seg[ver][rs]); 
      ch[ver][nd] = (ch[ver][nd + 1] == ch[ver][rs] ? ch[ver][rs] : -1); 
    }
     
    void push(int nd, int l, int r) {
      if (!lazy[nd]) return;
      ch[cnt][nd] = lazy[nd];
      for (int i = cnt; i >= 0; --i) {
        seg[i][nd] = ch[i][nd] == ch[cnt][nd]; 
      }
      if (l != r) {
        int mid = (l + r) >> 1;
        int rs = nd + ((mid - l + 1) << 1);
        lazy[nd + 1] = lazy[nd];
        lazy[rs] = lazy[nd]; 
      }
      lazy[nd] = 0;
    }
     
    void upd(int nd, int l, int r, int s, int e, int v) {
      push(nd, l, r); 
      if (l >= s && r <= e) {
        lazy[nd] = v; 
        push(nd, l, r);
        return;
      }
      int mid = (l + r) >> 1;
      int rs = nd + ((mid - l + 1) << 1);
      if (mid >= e) {
        push(rs, mid + 1, r); 
        upd(nd + 1, l, mid, s, e, v);
      } else {
        if (mid < s) {
          push(nd + 1, l, mid); 
          upd(rs, mid + 1, r, s, e, v);      
        } else {
          upd(nd + 1, l, mid, s, e, v);      
          upd(rs, mid + 1, r, s, e, v);      
        }
      }
      for (int i = 0; i <= cnt; ++i) {
        seg[i][nd] = seg[i][nd + 1] & seg[i][rs]; 
        ch[i][nd] = ch[i][nd + 1] == ch[i][rs] ? ch[i][rs] : -1;     
      } 
    }
     
    int main(){
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      int n;
      cin >> n; 
      for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < n; ++j) {
          char c;
          cin >> c;
          a[i][j] = (c == 'J' ? 1 : c == 'O' ? 2 : 3); 
        }
      }
      auto merge = [&](int x, int y, int z) {
        for (int i = 0; i < n; ++i) {
          a[z][i] = a[x][i] == a[y][i] ? a[y][i] : a[y][i] ^ a[x][i];
        }
      }; 
      for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
          for (int k = 0; k < 3; ++k) {
            if (i == j && j == k) {
              continue;
            }
            merge(i, j, cnt);
            merge(cnt, k, cnt); 
            cnt++; 
          }
        }
      }
      int q;
      cin >> q;
      for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;
        a[cnt][i] = (c == 'J' ? 1 : c == 'O' ? 2 : 3); 
      }
      for (int i = cnt; i >= 0; --i) {
        build(i, 0, 0, n - 1); 
      }
      bool ans = false;
      for (int i = 0; i < cnt; ++i) {
        ans |= seg[i][0] == 1; 
      }
      cout << (ans ? "Yes" : "No") << '\n'; 
      while (q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        char c;
        cin >> c;
        int x = (c == 'J' ? 1 : c == 'O' ? 2 : 3); 
        upd(0, 0, n - 1, l, r, x); 
        ans = false;
        for (int i = 0; i < cnt; ++i) {
          ans |= seg[i][0] == 1; 
        }
        cout << (ans ? "Yes" : "No") << '\n';
      }
      return 0;
    }

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 112724 KB Output is correct
2 Correct 166 ms 112716 KB Output is correct
3 Correct 240 ms 112784 KB Output is correct
4 Correct 126 ms 112828 KB Output is correct
5 Correct 129 ms 112720 KB Output is correct
6 Correct 164 ms 112724 KB Output is correct
7 Correct 123 ms 112720 KB Output is correct
8 Correct 164 ms 112652 KB Output is correct
9 Correct 132 ms 112780 KB Output is correct
10 Correct 140 ms 112720 KB Output is correct
11 Correct 135 ms 112912 KB Output is correct
12 Correct 130 ms 112644 KB Output is correct
13 Correct 154 ms 112640 KB Output is correct
14 Correct 159 ms 112648 KB Output is correct
15 Correct 142 ms 112720 KB Output is correct
16 Correct 133 ms 112720 KB Output is correct
17 Correct 171 ms 112768 KB Output is correct
18 Correct 180 ms 112744 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 112724 KB Output is correct
2 Correct 166 ms 112716 KB Output is correct
3 Correct 240 ms 112784 KB Output is correct
4 Correct 126 ms 112828 KB Output is correct
5 Correct 129 ms 112720 KB Output is correct
6 Correct 164 ms 112724 KB Output is correct
7 Correct 123 ms 112720 KB Output is correct
8 Correct 164 ms 112652 KB Output is correct
9 Correct 132 ms 112780 KB Output is correct
10 Correct 140 ms 112720 KB Output is correct
11 Correct 135 ms 112912 KB Output is correct
12 Correct 130 ms 112644 KB Output is correct
13 Correct 154 ms 112640 KB Output is correct
14 Correct 159 ms 112648 KB Output is correct
15 Correct 142 ms 112720 KB Output is correct
16 Correct 133 ms 112720 KB Output is correct
17 Correct 171 ms 112768 KB Output is correct
18 Correct 180 ms 112744 KB Output is correct
19 Correct 1720 ms 118988 KB Output is correct
20 Correct 1177 ms 118752 KB Output is correct
21 Correct 956 ms 119252 KB Output is correct
22 Correct 939 ms 118636 KB Output is correct
23 Correct 331 ms 113484 KB Output is correct
24 Correct 270 ms 113592 KB Output is correct
25 Correct 1014 ms 118968 KB Output is correct
26 Correct 1040 ms 119232 KB Output is correct
27 Correct 1133 ms 118864 KB Output is correct
28 Correct 1325 ms 119032 KB Output is correct
29 Correct 1184 ms 119000 KB Output is correct
30 Correct 318 ms 113488 KB Output is correct
31 Correct 1173 ms 119504 KB Output is correct
32 Correct 1199 ms 119136 KB Output is correct
33 Correct 268 ms 113488 KB Output is correct
34 Correct 1261 ms 119256 KB Output is correct
35 Correct 917 ms 116576 KB Output is correct
36 Correct 257 ms 113560 KB Output is correct
37 Correct 281 ms 113424 KB Output is correct
38 Correct 944 ms 119120 KB Output is correct
39 Correct 338 ms 118356 KB Output is correct
40 Correct 896 ms 116380 KB Output is correct
41 Correct 1913 ms 119588 KB Output is correct
42 Correct 111 ms 118316 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 112724 KB Output is correct
2 Correct 166 ms 112716 KB Output is correct
3 Correct 240 ms 112784 KB Output is correct
4 Correct 126 ms 112828 KB Output is correct
5 Correct 129 ms 112720 KB Output is correct
6 Correct 164 ms 112724 KB Output is correct
7 Correct 123 ms 112720 KB Output is correct
8 Correct 164 ms 112652 KB Output is correct
9 Correct 132 ms 112780 KB Output is correct
10 Correct 140 ms 112720 KB Output is correct
11 Correct 135 ms 112912 KB Output is correct
12 Correct 130 ms 112644 KB Output is correct
13 Correct 154 ms 112640 KB Output is correct
14 Correct 159 ms 112648 KB Output is correct
15 Correct 142 ms 112720 KB Output is correct
16 Correct 133 ms 112720 KB Output is correct
17 Correct 171 ms 112768 KB Output is correct
18 Correct 180 ms 112744 KB Output is correct
19 Correct 166 ms 112712 KB Output is correct
20 Correct 183 ms 112744 KB Output is correct
21 Correct 134 ms 112648 KB Output is correct
22 Correct 117 ms 112660 KB Output is correct
23 Correct 131 ms 112812 KB Output is correct
24 Correct 139 ms 113112 KB Output is correct
25 Correct 135 ms 112720 KB Output is correct
26 Correct 123 ms 112648 KB Output is correct
27 Correct 133 ms 112720 KB Output is correct
28 Correct 120 ms 112720 KB Output is correct
29 Correct 137 ms 112648 KB Output is correct
30 Correct 130 ms 112732 KB Output is correct
31 Correct 147 ms 112900 KB Output is correct
32 Correct 136 ms 112840 KB Output is correct
33 Correct 150 ms 112708 KB Output is correct
34 Correct 144 ms 112724 KB Output is correct
35 Correct 142 ms 112716 KB Output is correct
36 Correct 143 ms 112648 KB Output is correct
37 Correct 142 ms 112844 KB Output is correct
38 Correct 141 ms 112720 KB Output is correct
39 Correct 146 ms 112856 KB Output is correct
40 Correct 158 ms 112860 KB Output is correct
41 Correct 147 ms 112804 KB Output is correct
42 Correct 159 ms 112724 KB Output is correct
43 Correct 162 ms 112724 KB Output is correct
44 Correct 160 ms 112720 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 112724 KB Output is correct
2 Correct 166 ms 112716 KB Output is correct
3 Correct 240 ms 112784 KB Output is correct
4 Correct 126 ms 112828 KB Output is correct
5 Correct 129 ms 112720 KB Output is correct
6 Correct 164 ms 112724 KB Output is correct
7 Correct 123 ms 112720 KB Output is correct
8 Correct 164 ms 112652 KB Output is correct
9 Correct 132 ms 112780 KB Output is correct
10 Correct 140 ms 112720 KB Output is correct
11 Correct 135 ms 112912 KB Output is correct
12 Correct 130 ms 112644 KB Output is correct
13 Correct 154 ms 112640 KB Output is correct
14 Correct 159 ms 112648 KB Output is correct
15 Correct 142 ms 112720 KB Output is correct
16 Correct 133 ms 112720 KB Output is correct
17 Correct 171 ms 112768 KB Output is correct
18 Correct 180 ms 112744 KB Output is correct
19 Correct 1720 ms 118988 KB Output is correct
20 Correct 1177 ms 118752 KB Output is correct
21 Correct 956 ms 119252 KB Output is correct
22 Correct 939 ms 118636 KB Output is correct
23 Correct 331 ms 113484 KB Output is correct
24 Correct 270 ms 113592 KB Output is correct
25 Correct 1014 ms 118968 KB Output is correct
26 Correct 1040 ms 119232 KB Output is correct
27 Correct 1133 ms 118864 KB Output is correct
28 Correct 1325 ms 119032 KB Output is correct
29 Correct 1184 ms 119000 KB Output is correct
30 Correct 318 ms 113488 KB Output is correct
31 Correct 1173 ms 119504 KB Output is correct
32 Correct 1199 ms 119136 KB Output is correct
33 Correct 268 ms 113488 KB Output is correct
34 Correct 1261 ms 119256 KB Output is correct
35 Correct 917 ms 116576 KB Output is correct
36 Correct 257 ms 113560 KB Output is correct
37 Correct 281 ms 113424 KB Output is correct
38 Correct 944 ms 119120 KB Output is correct
39 Correct 338 ms 118356 KB Output is correct
40 Correct 896 ms 116380 KB Output is correct
41 Correct 1913 ms 119588 KB Output is correct
42 Correct 111 ms 118316 KB Output is correct
43 Correct 166 ms 112712 KB Output is correct
44 Correct 183 ms 112744 KB Output is correct
45 Correct 134 ms 112648 KB Output is correct
46 Correct 117 ms 112660 KB Output is correct
47 Correct 131 ms 112812 KB Output is correct
48 Correct 139 ms 113112 KB Output is correct
49 Correct 135 ms 112720 KB Output is correct
50 Correct 123 ms 112648 KB Output is correct
51 Correct 133 ms 112720 KB Output is correct
52 Correct 120 ms 112720 KB Output is correct
53 Correct 137 ms 112648 KB Output is correct
54 Correct 130 ms 112732 KB Output is correct
55 Correct 147 ms 112900 KB Output is correct
56 Correct 136 ms 112840 KB Output is correct
57 Correct 150 ms 112708 KB Output is correct
58 Correct 144 ms 112724 KB Output is correct
59 Correct 142 ms 112716 KB Output is correct
60 Correct 143 ms 112648 KB Output is correct
61 Correct 142 ms 112844 KB Output is correct
62 Correct 141 ms 112720 KB Output is correct
63 Correct 146 ms 112856 KB Output is correct
64 Correct 158 ms 112860 KB Output is correct
65 Correct 147 ms 112804 KB Output is correct
66 Correct 159 ms 112724 KB Output is correct
67 Correct 162 ms 112724 KB Output is correct
68 Correct 160 ms 112720 KB Output is correct
69 Correct 1459 ms 118628 KB Output is correct
70 Correct 1104 ms 118912 KB Output is correct
71 Correct 273 ms 113436 KB Output is correct
72 Correct 283 ms 113524 KB Output is correct
73 Correct 280 ms 113492 KB Output is correct
74 Correct 897 ms 118988 KB Output is correct
75 Correct 303 ms 113616 KB Output is correct
76 Correct 1008 ms 119580 KB Output is correct
77 Correct 975 ms 119032 KB Output is correct
78 Correct 280 ms 113504 KB Output is correct
79 Correct 286 ms 113488 KB Output is correct
80 Correct 907 ms 116508 KB Output is correct
81 Correct 287 ms 113360 KB Output is correct
82 Correct 1006 ms 118864 KB Output is correct
83 Correct 1032 ms 119428 KB Output is correct
84 Correct 350 ms 113364 KB Output is correct
85 Correct 302 ms 113708 KB Output is correct
86 Correct 1283 ms 116360 KB Output is correct
87 Correct 1312 ms 119120 KB Output is correct
88 Correct 411 ms 113360 KB Output is correct
89 Correct 1160 ms 118860 KB Output is correct
90 Correct 1404 ms 119120 KB Output is correct
91 Correct 359 ms 113364 KB Output is correct
92 Correct 892 ms 116560 KB Output is correct
93 Correct 323 ms 113492 KB Output is correct
94 Correct 345 ms 113548 KB Output is correct
95 Correct 291 ms 113552 KB Output is correct
96 Correct 964 ms 118956 KB Output is correct
97 Correct 380 ms 118564 KB Output is correct
98 Correct 905 ms 116756 KB Output is correct
99 Correct 1847 ms 119268 KB Output is correct
100 Correct 120 ms 118308 KB Output is correct