oj.uz

답안 #941311

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
941311 2024-03-08T13:27:54 Z haxorman Crossing (JOI21_crossing) C++14
26 / 100
 7000 ms 18560 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) + MOD) % MOD * 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:28: 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:20: 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:27: 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:27: warning: array subscript has type 'char' [-Wchar-subscripts]
  143 |         seg[SZ] = num[t[0]];
      |                           ^
Main.cpp:146:33: warning: array subscript has type 'char' [-Wchar-subscripts]
  146 |             seg[i+SZ] = num[t[i]] * p[i] % MOD;
      |                                 ^
Main.cpp:160:30: warning: array subscript has type 'char' [-Wchar-subscripts]
  160 |             update(l, r, num[c]);
      |                              ^

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 8536 KB Output is correct
2 Correct 142 ms 8560 KB Output is correct
3 Correct 303 ms 10608 KB Output is correct
4 Correct 135 ms 8532 KB Output is correct
5 Correct 133 ms 8528 KB Output is correct
6 Correct 123 ms 10496 KB Output is correct
7 Correct 129 ms 8528 KB Output is correct
8 Correct 139 ms 10664 KB Output is correct
9 Correct 135 ms 10840 KB Output is correct
10 Correct 144 ms 10580 KB Output is correct
11 Correct 133 ms 10684 KB Output is correct
12 Correct 146 ms 10580 KB Output is correct
13 Correct 134 ms 10576 KB Output is correct
14 Correct 135 ms 10576 KB Output is correct
15 Correct 132 ms 10580 KB Output is correct
16 Correct 136 ms 10664 KB Output is correct
17 Correct 134 ms 10576 KB Output is correct
18 Correct 286 ms 10584 KB Output is correct

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 8536 KB Output is correct
2 Correct 142 ms 8560 KB Output is correct
3 Correct 303 ms 10608 KB Output is correct
4 Correct 135 ms 8532 KB Output is correct
5 Correct 133 ms 8528 KB Output is correct
6 Correct 123 ms 10496 KB Output is correct
7 Correct 129 ms 8528 KB Output is correct
8 Correct 139 ms 10664 KB Output is correct
9 Correct 135 ms 10840 KB Output is correct
10 Correct 144 ms 10580 KB Output is correct
11 Correct 133 ms 10684 KB Output is correct
12 Correct 146 ms 10580 KB Output is correct
13 Correct 134 ms 10576 KB Output is correct
14 Correct 135 ms 10576 KB Output is correct
15 Correct 132 ms 10580 KB Output is correct
16 Correct 136 ms 10664 KB Output is correct
17 Correct 134 ms 10576 KB Output is correct
18 Correct 286 ms 10584 KB Output is correct
19 Execution timed out 7055 ms 18560 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 8536 KB Output is correct
2 Correct 142 ms 8560 KB Output is correct
3 Correct 303 ms 10608 KB Output is correct
4 Correct 135 ms 8532 KB Output is correct
5 Correct 133 ms 8528 KB Output is correct
6 Correct 123 ms 10496 KB Output is correct
7 Correct 129 ms 8528 KB Output is correct
8 Correct 139 ms 10664 KB Output is correct
9 Correct 135 ms 10840 KB Output is correct
10 Correct 144 ms 10580 KB Output is correct
11 Correct 133 ms 10684 KB Output is correct
12 Correct 146 ms 10580 KB Output is correct
13 Correct 134 ms 10576 KB Output is correct
14 Correct 135 ms 10576 KB Output is correct
15 Correct 132 ms 10580 KB Output is correct
16 Correct 136 ms 10664 KB Output is correct
17 Correct 134 ms 10576 KB Output is correct
18 Correct 286 ms 10584 KB Output is correct
19 Correct 139 ms 8532 KB Output is correct
20 Correct 289 ms 10912 KB Output is correct
21 Correct 144 ms 10584 KB Output is correct
22 Correct 123 ms 8468 KB Output is correct
23 Correct 142 ms 10644 KB Output is correct
24 Correct 143 ms 8692 KB Output is correct
25 Correct 139 ms 10588 KB Output is correct
26 Correct 129 ms 8572 KB Output is correct
27 Correct 142 ms 10676 KB Output is correct
28 Correct 126 ms 8528 KB Output is correct
29 Correct 139 ms 10580 KB Output is correct
30 Correct 128 ms 8568 KB Output is correct
31 Correct 169 ms 10580 KB Output is correct
32 Correct 141 ms 8744 KB Output is correct
33 Correct 135 ms 10740 KB Output is correct
34 Correct 120 ms 10576 KB Output is correct
35 Correct 145 ms 10576 KB Output is correct
36 Correct 135 ms 10716 KB Output is correct
37 Correct 149 ms 10768 KB Output is correct
38 Correct 150 ms 10576 KB Output is correct
39 Correct 180 ms 10656 KB Output is correct
40 Correct 144 ms 10784 KB Output is correct
41 Correct 141 ms 10576 KB Output is correct
42 Correct 135 ms 10572 KB Output is correct
43 Correct 141 ms 8788 KB Output is correct
44 Correct 138 ms 10576 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 8536 KB Output is correct
2 Correct 142 ms 8560 KB Output is correct
3 Correct 303 ms 10608 KB Output is correct
4 Correct 135 ms 8532 KB Output is correct
5 Correct 133 ms 8528 KB Output is correct
6 Correct 123 ms 10496 KB Output is correct
7 Correct 129 ms 8528 KB Output is correct
8 Correct 139 ms 10664 KB Output is correct
9 Correct 135 ms 10840 KB Output is correct
10 Correct 144 ms 10580 KB Output is correct
11 Correct 133 ms 10684 KB Output is correct
12 Correct 146 ms 10580 KB Output is correct
13 Correct 134 ms 10576 KB Output is correct
14 Correct 135 ms 10576 KB Output is correct
15 Correct 132 ms 10580 KB Output is correct
16 Correct 136 ms 10664 KB Output is correct
17 Correct 134 ms 10576 KB Output is correct
18 Correct 286 ms 10584 KB Output is correct
19 Execution timed out 7055 ms 18560 KB Time limit exceeded
20 Halted 0 ms 0 KB -