제출 #874960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
874960		efedmrlr	Crossing (JOI21_crossing)	C++17	26 / 100	216 ms	22344 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i)<(n); (i)++)

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 2e5+5;
const lli MOD = 1e9+7;
const lli INF = 1e12;
const int M = 1e6+5;
const long double EPS = 0.00001;
const lli PRIME = 5;
int n,m,q;
vector<int> s;
lli shash = 0;
lli pw[N];
lli powsm[N];

lli mult(lli x, lli y) {
    return x*y%MOD;
}
lli add(lli x, lli y) {
    return (x+y)%MOD;
}
lli subt(lli x, lli y) {
    if(x - y < 0) return x - y + MOD;
    return x - y;
}
lli find_pow_sum(int l, int r) {
    return subt(powsm[r] , (l > 0 ? powsm[l - 1] : 0ll));
}


struct SegTree {
    vector<lli> data, lazy;
    int sz;
    SegTree(int sz) {
        this->sz = sz;
        data.assign(4*(sz+5), 0);
        lazy.assign(4*(sz+5), -1);
    }
    void push(int tl, int tr, int v) {
        if(lazy[v] == -1) return;
        int tm = (tl + tr) >> 1;
        data[v*2] = mult(lazy[v] , find_pow_sum(tl, tm));
        data[v*2+1] = mult(lazy[v] , find_pow_sum(tm + 1, tr));
        lazy[v*2] = lazy[v];
        lazy[v*2+1] = lazy[v];
        lazy[v] = -1; 
    }

    void update(int tl, int tr, int v, int l, int r, int val) {
        if(tl >= l && tr <= r) {
            lazy[v] = val;
            data[v] = mult(val , find_pow_sum(tl, tr));
            return;
        }
        if(tl > r || tr < l) {
            return;
        }
        push(tl, tr, v);
        int tm = (tl + tr) >> 1;
        update(tl, tm, v*2, l, r, val);
        update(tm + 1, tr ,v*2+1, l, r, val);
        data[v] = add(data[v*2], data[v*2+1]);
    }
    void update(int l, int r, int val) {
        update(0, sz - 1, 1, l, r, val);
    }
    lli query(int tl, int tr, int v, int l, int r) {
        if(tl >= l && tr <= r) {
            return data[v];
        }
        if(tl > r || tr < l) {
            return 0;
        }
        push(tl, tr, v);
        int tm = (tl + tr) >> 1;
        return add(query(tl, tm, v*2, l, r), query(tm + 1, tr, v*2+1, l , r));
    }
    lli query(int l, int r) {
        return query(0, sz - 1, 1, l, r);
    }
};

void str_to_vec(string &src, vector<int> &nw) {
    nw.resize(src.size());
    for(int i = 0; i<src.size(); i++) {
        if(src[i] == 'J') nw[i] = 0;
        if(src[i] == 'O') nw[i] = 1;
        if(src[i] == 'I') nw[i] = 2;
    }
}


signed main() {
    //PREC
    powsm[0] = 1ll;
    pw[0] = 1ll;
    for(int i = 1; i<N; i++) {
        pw[i] = mult(pw[i - 1], PRIME);
        powsm[i] = powsm[i - 1] + pw[i];
    }
    fastio();
    cin>>n;
    string A;
    cin>>A;
    cin>>A;
    cin>>A;
    str_to_vec(A, s);

    cin>>q;
    vector<int> t0;
    cin>>A;
    str_to_vec(A, t0);
    SegTree st(n);
    for(int i = 0; i<n; i++) {
        shash = add(shash, mult(s[i], pw[i]));
    }
    for(int i = 0; i<n; i++) {
        st.update(i, i, t0[i]);
    }
    if(st.query(0, n - 1) == shash) {
        cout<<"Yes\n";
    }
    else {
        cout<<"No\n";
    }
    for(int i = 0; i<q; i++) {
        int l,r, cr;
        char c;
        cin>>l>>r>>c;
        l--; r--;
        if(c == 'J') cr = 0;
        if(c == 'O') cr = 1;
        if(c == 'I') cr = 2;
        st.update(l,r,cr);
        lli hs = st.query(0, n - 1);
        if(hs == shash) {
            cout<<"Yes\n";
        }
        else {
            cout<<"No\n";
        }
        
        
    }


}

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

Main.cpp: In function 'void str_to_vec(std::string&, std::vector<int>&)':
Main.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i = 0; i<src.size(); i++) {
      |                    ~^~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:62:23: warning: 'cr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |             lazy[v] = val;
      |                       ^~~
Main.cpp:138:18: note: 'cr' was declared here
  138 |         int l,r, cr;
      |                  ^~

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51