Submission #75817122

---

Source Code Expand

#include <bits/stdc++.h>
#pragma warning(disable:4996)
#pragma comment(linker,"/STACK:336777216")
#pragma GCC optimize("03,unroll-loops")
#pragma GCC target("avx,avx2,fma")

using namespace std;
using ll = long long;
using vl = vector<ll>;
using pll = pair<ll,ll>;

ll POW(ll a,ll b,ll rem) {
    ll p=1;
    a %= rem;
    for (;b;b>>=1,a=(a*a)%rem) {
        if (b&1)p = (p*a)%rem;
    }
    return p;
}

tuple<ll,ll,ll> extended_gcd(ll a,ll b) {
    if (a==0) return {b,0,1};
    auto [g,x,y] = extended_gcd(b%a,a);
    return {g,y-(b/a)*x,x};
}
ll modinverse(ll a ,ll m) {
    return (get<1>(extended_gcd(a,m))%m+m)%m;
}

void pre() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

void pre2() {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
}

void presolve() {

}

struct Data {
    ll val;
    ll lcnt,rcnt;
    bool connect;
    Data operator+(const Data&r)const {
        if (connect && r.connect)return {val + r.val,lcnt+r.rcnt,lcnt+r.rcnt,true};
        if (connect)return {val + r.val,lcnt+r.lcnt,r.rcnt,false};
        if (r.connect)return {val + r.val,lcnt,rcnt+r.rcnt,false};
        return {(rcnt+r.lcnt+1)/2 + val + r.val,lcnt,r.rcnt,false};
    }
};

template <typename T>
struct Seg {
    ll two;
    T init;
    vector<T> seg;
    Seg(int _n) :init(T()){
        two=1;
        while (two<_n)two<<=1;
        seg.assign(two<<1,init);
    }
    Seg(int _n, T _init) :init(_init){
        two=1;
        while (two<_n)two<<=1;
        seg.assign(two<<1,init);
    }
    void update(ll g,ll s,ll e,ll t,T val) {
        if (e<t||t<s)return;
        if (s==e) {
            seg[g] = val;
            return;
        }
        ll m = s+e>>1;
        update(g<<1,s,m,t,val);update((g<<1)+1,m+1,e,t,val);
        seg[g] = seg[g<<1]+seg[(g<<1)+1];
    }
    T find(ll g,ll s,ll e,ll ts,ll te) {
        if (e<ts||te<s)return init;
        if (ts<=s&&e<=te) {
            return seg[g];
        }
        ll m = s+e>>1;
        return (find(g<<1,s,m,ts,te)+find((g<<1)+1,m+1,e,ts,te));
    }
    void Update(ll t,T val) {
        update(1,1,two,t,val);
    }
    T Find(ll l,ll r) {
        if(l>r)return init;
        return find(1,1,two,l,r);
    }
};
void solve() {
    ll N,Q;
    cin>>N>>Q;
    string str;
    cin>>str;
    vl d(N-1);
    for (int i=0;i<N-1;i++) {
        d[i] = (str[i]==str[i+1]&&str[i]!='X')?1:0;
    }

    Seg<Data> seg(N-1,{0,0,0,false});

    for (int i=0;i<N-1;i++)seg.Update(i+1,{0,d[i],d[i],d[i]==1});

    for (int i=0;i<Q;i++) {
        ll l,r;
        cin>>l>>r;
        auto res = seg.Find(l,r-1);
        if (res.connect)cout<<res.val+(res.lcnt+1)/2<<"\n";
        else cout<<res.val+(res.lcnt+1)/2+(res.rcnt+1)/2<<"\n";
    }
}

int main() {
    pre();

    presolve();

    ll t=1;
    //cin>>t;
    while (t--) solve();
}

Submission Info

Compile Error

./Main.cpp:2: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    2 | #pragma warning(disable:4996)
./Main.cpp:3: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    3 | #pragma comment(linker,"/STACK:336777216")
./Main.cpp: In instantiation of 'void Seg<T>::update(ll, ll, ll, ll, T) [with T = Data; ll = long long int]':
./Main.cpp:91:9:   required from 'void Seg<T>::Update(ll, T) [with T = Data; ll = long long int]'
   91 |         update(1,1,two,t,val);
      |         ^~~~~~
./Main.cpp:110:38:   required from here
  110 |     for (int i=0;i<N-1;i++)seg.Update(i+1,{0,d[i],d[i],d[i]==1});
      |                            ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp:78:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |         ll m = s+e>>1;
      |                ~^~
./Main.cpp: In instantiation of 'T Seg<T>::find(ll, ll, ll, ll, ll) [with T = Data; ll = long long int]':
./Main.cpp:95:16:   required from 'T Seg<T>::Find(ll, ll) [with T = Data; ll = long long int]'
   95 |         return find(1,1,two,l,r);
      |                ^~~~
./Main.cpp:115:28:   required from here
  115 |         auto res = seg.Find(l,r-1);
      |                    ~~~~~~~~^~~~~~~
./Main.cpp:87:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         ll m = s+e>>1;
      |                ~^~

Judge Result