Submission #1193214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193214		DobromirAngelov	Crossing (JOI21_crossing)	C++20	100 / 100	251 ms	23832 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MAXN=2e5+5;
const int B=137;
const int MOD=1e9+7;

int n,q;
vector<vector<int> > v;
vector<int> hashes;
vector<int> a;
long long bpw[MAXN];
long long oneH[MAXN];

void precomp()
{
    bpw[0]=1;
    for(int i=1;i<=n;i++) bpw[i]=bpw[i-1]*B%MOD;
    oneH[0]=0;
    for(int i=1;i<=n;i++) oneH[i]=(oneH[i-1]+bpw[i-1])%MOD;
}

struct SegmentTree
{
    struct Node
    {
        long long h;
        int len;
        Node() {};
        Node(long long _h,int _len)
        {
            h=_h;
            len=_len;
        }
    };
    Node tree[4*MAXN];
    int lazy[4*MAXN];

    void init()
    {
        fill(tree,tree+4*n+1,Node(0,0));
    }

    Node combine(Node x,Node y)
    {
        int h=(x.h*bpw[y.len]+y.h)%MOD;
        int len=x.len+y.len;
        return Node(h,len);
    }

    void build(int node,int l,int r)
    {
        if(l==r)
        {
            tree[node].h=a[l];
            tree[node].len=1;
            return;
        }
        int mid=(l+r)/2;
        build(2*node,l,mid);
        build(2*node+1,mid+1,r);
        tree[node]=combine(tree[2*node], tree[2*node+1]);
    }

    int calcOneHash(int val,int len)
    {
        return oneH[len]*val%MOD;
    }

    void push(int node,int l,int r)
    {
        if(lazy[node]==0) return;
        if(l!=r)
        {
            tree[2*node].h=calcOneHash(lazy[node],tree[2*node].len);
            tree[2*node+1].h=calcOneHash(lazy[node],tree[2*node+1].len);
            lazy[2*node]=lazy[2*node+1]=lazy[node];
        }
        lazy[node]=0;
    }

    void update(int node,int l,int r,int ql,int qr,int val)
    {
        if(ql<=l && r<=qr)
        {
            tree[node].h=calcOneHash(val, tree[node].len);
            lazy[node]=val;
            return;
        }
        push(node,l,r);
        int mid=(l+r)/2;
        if(ql<=mid) update(2*node,l,mid,ql,qr,val);
        if(mid<qr) update(2*node+1,mid+1,r,ql,qr,val);
        tree[node]=combine(tree[2*node], tree[2*node+1]);
    }
};
SegmentTree tree;

int getHash(vector<int> a)
{
    long long ret=0;
    for(auto x: a)
    {
        ret=(ret*B+x)%MOD;
    }
    return ret;
}

int val(char c)
{
    if(c=='O') return 1;
    if(c=='I') return 2;
    else return 3;
}

vector<int> toArr(string s)
{
    vector<int> ret(s.size());
    for(int i=0;i<s.size();i++) ret[i]=val(s[i]);
    return ret;
}

vector<int> cross(vector<int> a,vector<int> b)
{
    vector<int> ret(a.size());
    for(int i=0;i<a.size();i++)
    {
        if(a[i]==b[i]) ret[i]=a[i];
        else ret[i]=6-a[i]-b[i];
    }
    return ret;
}

bool eq(vector<int> a,vector<int> b)
{
    for(int i=0;i<a.size();i++)
        if(a[i]!=b[i]) return 0;
    return 1;
}

string query()
{
    int cur=tree.tree[1].h;
    for(auto x: hashes)
    {
        if(x==cur) return "Yes";
    }
    return "No";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n;
    for(int i=0;i<3;i++)
    {
        string s;
        cin>>s;
        vector<int> cur=toArr(s);
        if(v.empty()) v.push_back(cur);
        else
        {
            bool fl=0;
            for(auto x: v)
            {
                if(eq(x,cur)) fl=1;
            }
            if(!fl) v.push_back(cur);
        }
    }

    for(int i=0;i<v.size();i++)
    {
        for(int j=i+1;j<v.size();j++)
        {
            vector<int> cur=cross(v[i],v[j]);
            bool fl=0;
            for(auto x: v)
            {
                if(eq(x,cur)) fl=1;
            }
            if(!fl) v.push_back(cur);
        }
    }

    precomp();
    for(auto x: v)
    {
        hashes.push_back(getHash(x));
    }

    cin>>q;
    string s;
    cin>>s;
    a=toArr(s);
    tree.build(1,0,n-1);
    cout<<query()<<endl;
    for(int i=0;i<q;i++)
    {
        int l,r;
        char c;
        cin>>l>>r>>c;
        l--; r--;
        tree.update(1,0,n-1,l,r,val(c));
        cout<<query()<<endl;
    }

    return 0;
}

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