제출 #608996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
608996		kakayoshi	Crossing (JOI21_crossing)	C++17	26 / 100	356 ms	16368 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
typedef pair<int, pair<int,int> > piii;
typedef pair<pair<ll,ll> ,pair<ll, ll> > plll;
typedef vector <ll> vi;
#define forw(i,a,b) for (ll i=a;i<=(b);i++)
#define forb(i,a,b) for (ll i=a;i>=(b);i--)
#define fastIO {ios::sync_with_stdio(false); cin.tie(0); }
#define fi first
#define se second
#define pu push
#define puf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fr front
#define all(a) a.begin(),a.end()
const ll oo=1e18;
const ll mod=1e9+7;
const int base=31;
const ll maxN=3e5+5;
const int tx[4]={0,1,0,-1};
const int ty[4]={1,0,-1,0};
const ll maxM=maxN*4+5;
const ll block=500;
#define mul(a,b) (a*b)%mod
#define add(a,b) (a+b)%mod
ll pre[maxN],n,key,q;
string s1,s2,s3,s4;
struct segment
{
    vector <ll> seg,lazy;
    segment(int n)
    {
        seg.assign(4*n+5,0);
        lazy.assign(4*n+5,0);
    }
    ll get_pre(int l, int r)
    {
        ll ans=pre[r];
        if (l>0) ans=(ans-pre[l-1]+mod)%mod;
        return ans;
    }
    void down(int id, int l, int r, int mid)
    {
        if (!lazy[id]) return;
        seg[id*2]=mul(get_pre(l-1,mid-1),lazy[id]);
        lazy[id*2]=lazy[id];
        seg[id*2+1]=mul(get_pre(mid,r-1),lazy[id]);
        lazy[id*2+1]=lazy[id];
        lazy[id]=0;
        return;
    }
    void update(int id, int l, int r, int u, int v, ll val)
    {
        if (v<l || r<u) return;
        if (u<=l && r<=v)
        {
            seg[id]=mul(get_pre(l-1,r-1),val);
            lazy[id]=val;
            return;
        }
        int  mid=(l+r)/2;
        down(id,l,r,mid);
        update(id*2,l,mid,u,v,val);
        update(id*2+1,mid+1,r,u,v,val);
        seg[id]=add(seg[id*2],seg[id*2+1]);
        return;
    }
};
ll get(char c)
{
    if (c=='J') return 1;
    if (c=='O') return 2;
    return 3;
}
void solve()
{
    cin>>n;
    cin>>s1>>s2>>s3;
    cin>>q;
    cin>>s4;
    ll tmp=1;
    //power[0]=1;
    pre[0]=1;
    segment seg(n);
    forw(i,1,n)
    {
        //power[i]=mul(power[i-1],5);
        key=add(key,mul(get(s1[i-1]),tmp));
        tmp=mul(tmp,5);
        pre[i]=add(pre[i-1],tmp);
        seg.update(1,1,n,i,i,get(s4[i-1]));
    }
    //cout<<key<<endl;
    if (seg.seg[1]==key) cout<<"Yes\n";
    else cout<<"No\n";
    while (q--)
    {
        int l,r; char c; cin>>l>>r>>c;
        seg.update(1,1,n,l,r,get(c));
        if (seg.seg[1]==key) cout<<"Yes\n";
        else cout<<"No\n";
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("a.inp","r",stdin);
    //freopen("a.out","w",stdout);
    solve();
    return 0;
}

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