제출 #941311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
941311		haxorman	Crossing (JOI21_crossing)	C++14	26 / 100	7055 ms	18560 KiB

Main

    #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");
        }
    }

컴파일 시 표준 에러 (stderr) 메시지

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 / 3
• Subtask 2: 0 / 23
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51