Submission #1055369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055369		YassirSalama	Crossing (JOI21_crossing)	C++17	3 / 100	303 ms	28612 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int P=31;
const int maxn=2e5+100;
int pref[maxn];
struct Node{
    int val;
    int lz;
    Node* left,*right;
    Node() : left(nullptr),right(nullptr){}
};
int f(int a){
    a%=mod;
    if(a<0) a+=mod;
    return a%=mod;
}
int sum(int l,int r){
    if(l==0) return pref[r];
    return f(pref[r]%mod-pref[l-1]%mod)%mod;
}
void push(Node* node,int l,int r){
    if(node->lz==0) return;
    node->val=f(node->lz*f(sum(l,r))%mod);
    if(l!=r){
        node->left->lz=node->lz;
        node->right->lz=node->lz;
    }
    node->lz=0;
}
void p(Node* node,int l,int r){
    push(node,l,r);
    int mid=(l+r)/2;
    if(l==r) return;
    push(node->left,l,mid);
    push(node->right,mid+1,r);
}
void build(Node* node,int l,int r,vector<int> &v){
    if(l==r){
        node->val=v[l];
        return;
    }
    int mid=(l+r)/2;
    node->left=new Node();
    node->right=new Node();
    build(node->left,l,mid,v);
    build(node->right,mid+1,r,v);
    node->val=((node->left->val%mod)+(node->right->val%mod))%mod;
}
void update(Node* node,int l,int r,int ql,int qr,int x){
    p(node,l,r);
    if(ql<=l&&r<=qr){
        node->lz=x;p(node,l,r);
        return;
    }
    int mid=(l+r)>>1;
    if(ql<=mid){
        update(node->left,l,mid,ql,qr,x);
    }
    if(qr>mid) update(node->right,mid+1,r,ql,qr,x);
    node->val=((node->left->val%mod)+(node->right->val%mod))%mod;
}
int query(Node* node,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return node->val%mod;
    int mid=(l+r)/2;
    int ans=0;
    if(ql<=mid) ans=f(ans+query(node->left,l,mid,ql,qr)),ans%=mod;
    if(qr>mid) ans=f(ans+query(node->right,mid+1,r,ql,qr)),ans%=mod;
    return ans%mod;
}
map<char,int> mp;
vector<int> hsh(string s){
    int n=s.length();
    int c=1;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        int x=mp[s[i]];
        v[i]=(x*c%mod)%mod;
        c=(c*P%mod)%mod;
    }
    return v;
}

int binpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) {
            res=(res*a%mod)%mod;
        }
        a=(a*a%mod)%mod;
        b>>=1;
    }
    return res;
}
#define all(v) v.begin(),v.end()
signed main(){
    mp['J']=1;mp['O']=2;mp['I']=3;
    ios_base::sync_with_stdio(0);cin.tie(0);
    for(int i=0;i<maxn;i++){
        pref[i]=binpow(P,i)%mod;
        if(i) {
            pref[i]+=pref[i-1];
            pref[i]%=mod;
        }
    }
    int n;
    cin>>n;
    string s;
    cin>>s>>s>>s;
    int q;
    cin>>q;
    string t;
    cin>>t;
    vector<int> a=hsh(s);
    vector<int> b=hsh(t);
    int ans=0;
    for(auto x:a){
        ans+=x;
        ans%=mod;
    }
    Node* r1=new Node();
    build(r1,0,n-1,b);
    puts((r1->val==ans?"Yes":"No"));
    while(q--){
        int l,r;
        cin>>l>>r,--l,--r;char c;cin>>c;
        update(r1,0,n-1,l,r,mp[c]);
        puts((r1->val%mod==ans?"Yes":"No"));
    }
}

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