oj.uz

Submission #940503

# Submission time Handle Problem Language Result Execution time Memory
940503 2024-03-07T10:03:48 Z haxorman Crossing (JOI21_crossing) C++14
0 / 100
 236 ms 10612 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mxN = 2e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
const int MOD = 1e9 + 7;

int n, p[mxN], num[130], seg[4*mxN], lazy[4*mxN], def[mxN];

string cross(string a, string b) {
    string res;
    for (int i = 0; i < n; ++i) {
        if (a[i] == b[i]) {
            res += a[i];
            continue;
        }

        set<char> ch;
        ch.insert(a[i]);
        ch.insert(b[i]);

        for (auto c : {'J', 'O', 'I'}) {
            if (!ch.count(c)) {
                res += c;
                break;
            }
        }
    }
    return res;
}

void push(int ind, int l, int r, int cnt=1) {
    if (!lazy[ind]) {
        return;
    }
    seg[ind] = (def[r] - (l ? def[l-1] : 0)) * lazy[ind] % MOD;

    if (l != r) {
        lazy[2*ind] = lazy[ind];
        lazy[2*ind+1] = lazy[ind];

        if (cnt) {
            int mid = (l+r)/2;
            push(2*ind,l,mid);
            push(2*ind+1,mid+1,r);
        }
    }
    lazy[ind] = 0;
}

void update(int lo, int hi, int val, int ind=1, int l=0, int r=SZ-1) {
    push(ind,l,r);
    if (lo > r || l > hi) {
        return;
    }

    if (lo <= l && r <= hi) {
        lazy[ind] = val;
        push(ind,l,r);
        return;
    }

    int mid = (l+r)/2;
    update(lo,hi,val,2*ind,l,mid);
    update(lo,hi,val,2*ind+1,mid+1,r);

    seg[ind] = (seg[2*ind] + seg[2*ind+1]) % MOD;
}

int query(int lo, int hi, int ind=1, int l=0, int r=SZ-1) {
    push(ind,l,r);
    if (lo > r || l > hi) {
        return 0;
    }

    if (lo <= l && r <= hi) {
        return seg[ind];
    }

    int mid = (l+r)/2;
    return (query(lo,hi,2*ind,l,mid) + query(lo,hi,2*ind+1,mid+1,r)) % MOD;
}

int hsh(string s) {
    int res = 0;
    for (int i = 0; i < n; ++i) {
        res += num[s[i]] * p[i] % MOD;
        res %= MOD;
    }
    return res;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    num['J'] = 1, num['O'] = 2, num['I'] = 3;

    p[0] = 1;
    for (int i = 1; i < n; ++i) {
        p[i] = p[i-1] * 31 % MOD;
    }
    
    set<string> check;
    vector<string> s;
    for (int i = 0; i < 3; ++i) {
        string str;
        cin >> str;

        if (!check.count(str)) {
            s.push_back(str);
            check.insert(str);
        }
    }
    
    int ind = 0;
    while (ind < s.size()) {
        int len = s.size();
        for (int i = 0; i < len; ++i) {
            string str = cross(s[ind], s[i]);
            if (!check.count(str)) {
                s.push_back(str);
                check.insert(str);
            }
        }
        ++ind;
    }
     
    set<int> fin;
    for (int i = 0; i < s.size(); ++i) {
        fin.insert(hsh(s[i]));
    }

    int q;
    cin >> q;

    string t;
    cin >> t;
    
    def[0] = 1;
    seg[SZ] = num[t[0]];
    for (int i = 1; i < n; ++i) {
        def[i] = (def[i-1] + p[i]) % MOD;
        seg[i+SZ] = num[t[i]] * p[i] % MOD;
    }
    
    for (int i = SZ-1; i >= 0; --i) {
        seg[i] = (seg[2*i] + seg[2*i+1]) % MOD;
    }
    
    cout << (fin.count(query(0,n-1)) ? "Yes\n" : "No\n");
    while (q--) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        --l, --r;
        
        update(l, r, num[c]);
        cout << (fin.count(query(0,n-1)) ? "Yes\n" : "No\n");
    }
}

Compilation message

Main.cpp: In function 'long long int hsh(std::string)':
Main.cpp:89:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   89 |         res += num[s[i]] * p[i] % MOD;
      |                        ^
Main.cpp: In function 'int32_t main()':
Main.cpp:119:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     while (ind < s.size()) {
      |            ~~~~^~~~~~~~~~
Main.cpp:132:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i = 0; i < s.size(); ++i) {
      |                     ~~^~~~~~~~~~
Main.cpp:143:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  143 |     seg[SZ] = num[t[0]];
      |                       ^
Main.cpp:146:29: warning: array subscript has type 'char' [-Wchar-subscripts]
  146 |         seg[i+SZ] = num[t[i]] * p[i] % MOD;
      |                             ^
Main.cpp:160:26: warning: array subscript has type 'char' [-Wchar-subscripts]
  160 |         update(l, r, num[c]);
      |                          ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 8596 KB Output is correct
2 Correct 139 ms 8528 KB Output is correct
3 Correct 236 ms 10580 KB Output is correct
4 Correct 129 ms 8492 KB Output is correct
5 Correct 127 ms 8532 KB Output is correct
6 Incorrect 123 ms 10612 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 8596 KB Output is correct
2 Correct 139 ms 8528 KB Output is correct
3 Correct 236 ms 10580 KB Output is correct
4 Correct 129 ms 8492 KB Output is correct
5 Correct 127 ms 8532 KB Output is correct
6 Incorrect 123 ms 10612 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 8596 KB Output is correct
2 Correct 139 ms 8528 KB Output is correct
3 Correct 236 ms 10580 KB Output is correct
4 Correct 129 ms 8492 KB Output is correct
5 Correct 127 ms 8532 KB Output is correct
6 Incorrect 123 ms 10612 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 8596 KB Output is correct
2 Correct 139 ms 8528 KB Output is correct
3 Correct 236 ms 10580 KB Output is correct
4 Correct 129 ms 8492 KB Output is correct
5 Correct 127 ms 8532 KB Output is correct
6 Incorrect 123 ms 10612 KB Output isn't correct
7 Halted 0 ms 0 KB -