oj.uz

Submission #501671

# Submission time Handle Problem Language Result Execution time Memory
501671 2022-01-04T09:46:21 Z tengiz05 Crossing (JOI21_crossing) C++17
3 / 100
 7000 ms 43760 KB 
#include <bits/stdc++.h>

using i64 = long long;

int pre[9][3][200005];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    auto in = [&]() {
        std::string a;
        std::cin >> a;
        std::vector<int> b(n);
        for (int i = 0; i < n; i++) {
            b[i] = std::string("JOI").find(a[i]);
        }
        return b;
    };
    
    std::vector<int> a = in(), b = in(), c = in();
    
    auto merge = [&](std::vector<int> a, std::vector<int> b) {
        auto c = a;
        for (int i = 0; i < n; i++) {
            if (a[i] != b[i]) {
                c[i] = 0 ^ 1 ^ 2 ^ a[i] ^ b[i];
            }
        }
        return c;
    };
    
    std::vector<std::vector<int>> s{a, b, c, merge(a, b), merge(a, c), merge(b, c), merge(merge(a, c), b), merge(merge(a, b), c), merge(merge(b, c), a)};
    
    int q;
    std::cin >> q;
    std::vector<int> t = in();
    
    for (int k = 0; k < 9; k++) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < n; j++) {
                pre[k][i][j + 1] = pre[k][i][j] + (s[k][j] == i);
            }
        }
    }
    
    int bad[9] {};
    for (int k = 0; k < 9; k++)
        for (int i = 0; i < n; i++)
            bad[k] += t[i] != s[k][i];
    
    std::set<std::pair<int, int>> p{{-1, -1}, {n, -1}};
    for (int i = 0; i < n; i++)
        p.emplace(i, t[i]);
    
    int ok = 0;
    for (int k = 0; k < 9; k++) {
        ok += bad[k] == 0;
    }
    if (ok) {
        std::cout << "Yes\n";
    } else {
        std::cout << "No\n";
    }
    
    auto rem = [&](int l, int r, int c) {
        for (int k = 0; k < 9; k++) {
            bad[k] -= (pre[k][c][r] - pre[k][c][l] != r - l);
        }
    };
    auto add = [&](int l, int r, int c) {
        for (int k = 0; k < 9; k++) {
            bad[k] += (pre[k][c][r] - pre[k][c][l] != r - l);
        }
    };
    
    while (q--) {
        int l, r;
        char ch;
        std::cin >> l >> r >> ch;
        l--;
        
        int x = std::string("JOI").find(ch);
        
        for (int i = l; i < r; i++) {
            t[i] = x;
        }
        
        if (s[0] == t) {
            std::cout << "Yes\n";
        } else {
            std::cout << "No\n";
        }
        
        // auto it = p.lower_bound({l, -1});
        // if (it->first > l) {
            // int L = std::prev(it)->first;
            // int R = it->first;
            // int c = std::prev(it)->second;
            // rem(L, R, c);
            // add(L, l, c);
            // add(l, R, c);
            // p.emplace(l, c);
        // }
        
        // it = p.lower_bound({r, -1});
        // if (it->first > r) {
            // int L = std::prev(it)->first;
            // int R = it->first;
            // int c = std::prev(it)->second;
            // rem(L, R, c);
            // add(L, r, c);
            // add(r, R, c);
            // p.emplace(r, c);
        // }
        
        // assert(p.lower_bound({l, -1})->first == l);
        // while (true) {
            // it = p.lower_bound({l, -1});
            // if (it->first < r) {
                // rem(it->first, std::next(it)->first, it->second);
                // p.erase(it);
            // } else {
                // break;
            // }
        // }
        
        // add(l, r, x);
        // p.emplace(l, x);
        
        // int ok = 0;
        // for (int k = 0; k < 9; k++) {
            // ok += bad[k] == 0;
        // }
        // if (ok) {
            // std::cout << "Yes\n";
        // } else {
            // std::cout << "No\n";
        // }
    }
    
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:69:10: warning: variable 'rem' set but not used [-Wunused-but-set-variable]
   69 |     auto rem = [&](int l, int r, int c) {
      |          ^~~
Main.cpp:74:10: warning: variable 'add' set but not used [-Wunused-but-set-variable]
   74 |     auto add = [&](int l, int r, int c) {
      |          ^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1436 KB Output is correct
2 Correct 40 ms 2508 KB Output is correct
3 Correct 44 ms 2456 KB Output is correct
4 Correct 41 ms 2532 KB Output is correct
5 Correct 41 ms 2508 KB Output is correct
6 Correct 40 ms 2380 KB Output is correct
7 Correct 39 ms 2512 KB Output is correct
8 Correct 38 ms 2564 KB Output is correct
9 Correct 38 ms 2596 KB Output is correct
10 Correct 44 ms 2608 KB Output is correct
11 Correct 43 ms 2588 KB Output is correct
12 Correct 40 ms 2592 KB Output is correct
13 Correct 39 ms 2596 KB Output is correct
14 Correct 48 ms 2524 KB Output is correct
15 Correct 43 ms 2572 KB Output is correct
16 Correct 38 ms 2612 KB Output is correct
17 Correct 40 ms 2556 KB Output is correct
18 Correct 47 ms 2432 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1436 KB Output is correct
2 Correct 40 ms 2508 KB Output is correct
3 Correct 44 ms 2456 KB Output is correct
4 Correct 41 ms 2532 KB Output is correct
5 Correct 41 ms 2508 KB Output is correct
6 Correct 40 ms 2380 KB Output is correct
7 Correct 39 ms 2512 KB Output is correct
8 Correct 38 ms 2564 KB Output is correct
9 Correct 38 ms 2596 KB Output is correct
10 Correct 44 ms 2608 KB Output is correct
11 Correct 43 ms 2588 KB Output is correct
12 Correct 40 ms 2592 KB Output is correct
13 Correct 39 ms 2596 KB Output is correct
14 Correct 48 ms 2524 KB Output is correct
15 Correct 43 ms 2572 KB Output is correct
16 Correct 38 ms 2612 KB Output is correct
17 Correct 40 ms 2556 KB Output is correct
18 Correct 47 ms 2432 KB Output is correct
19 Correct 1892 ms 43760 KB Output is correct
20 Execution timed out 7060 ms 42840 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1436 KB Output is correct
2 Correct 40 ms 2508 KB Output is correct
3 Correct 44 ms 2456 KB Output is correct
4 Correct 41 ms 2532 KB Output is correct
5 Correct 41 ms 2508 KB Output is correct
6 Correct 40 ms 2380 KB Output is correct
7 Correct 39 ms 2512 KB Output is correct
8 Correct 38 ms 2564 KB Output is correct
9 Correct 38 ms 2596 KB Output is correct
10 Correct 44 ms 2608 KB Output is correct
11 Correct 43 ms 2588 KB Output is correct
12 Correct 40 ms 2592 KB Output is correct
13 Correct 39 ms 2596 KB Output is correct
14 Correct 48 ms 2524 KB Output is correct
15 Correct 43 ms 2572 KB Output is correct
16 Correct 38 ms 2612 KB Output is correct
17 Correct 40 ms 2556 KB Output is correct
18 Correct 47 ms 2432 KB Output is correct
19 Correct 37 ms 2508 KB Output is correct
20 Correct 49 ms 2476 KB Output is correct
21 Incorrect 43 ms 2500 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1436 KB Output is correct
2 Correct 40 ms 2508 KB Output is correct
3 Correct 44 ms 2456 KB Output is correct
4 Correct 41 ms 2532 KB Output is correct
5 Correct 41 ms 2508 KB Output is correct
6 Correct 40 ms 2380 KB Output is correct
7 Correct 39 ms 2512 KB Output is correct
8 Correct 38 ms 2564 KB Output is correct
9 Correct 38 ms 2596 KB Output is correct
10 Correct 44 ms 2608 KB Output is correct
11 Correct 43 ms 2588 KB Output is correct
12 Correct 40 ms 2592 KB Output is correct
13 Correct 39 ms 2596 KB Output is correct
14 Correct 48 ms 2524 KB Output is correct
15 Correct 43 ms 2572 KB Output is correct
16 Correct 38 ms 2612 KB Output is correct
17 Correct 40 ms 2556 KB Output is correct
18 Correct 47 ms 2432 KB Output is correct
19 Correct 1892 ms 43760 KB Output is correct
20 Execution timed out 7060 ms 42840 KB Time limit exceeded
21 Halted 0 ms 0 KB -