Submission #881355

#	Time	Username	Problem	Language	Result	Execution time	Memory
881355		1L1YA	Crossing (JOI21_crossing)	C++17	26 / 100	7025 ms	5880 KiB

Main

//1L1YA
#include<bits/stdc++.h>
using namespace std;
#define ll           long long
#define Pb           push_back
#define dokme(x)     cout << x << endl, exit(0)
#define pii          pair<int,int>
#define F            first
#define S            second
#define endl         '\n'
#define sep          ' '
#define all(x)       x.begin(),x.end()
#define FastIO       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lc           id<<1
#define rc           lc|1

const ll mod=1e9+7;
const ll oo=4e18;
const int N=2e5+5;
const int lg=23;

int n,q;
string t,s[3][3];

void change(string &s){
    for(int i=1;i<=n;i++)
        if(s[i]=='J')
            s[i]='b';
        else if(s[i]=='O')
            s[i]='c';
        else
            s[i]='d';
}

int main(){
    FastIO

    cin >> n >> s[0][0] >> s[0][1] >> s[0][2];
    s[0][0]='#'+s[0][0];s[0][1]='#'+s[0][1];s[0][2]='#'+s[0][2];
    change(s[0][0]);change(s[0][1]);change(s[0][2]);
    for(int k=1;k<3;k++){
        s[k][0]=s[k-1][0];s[k][1]=s[k-1][1];s[k][2]=s[k-1][2];
        for(int i=1;i<=n;i++){
            if(s[k-1][1][i]==s[k-1][2][i])
                s[k][0][i]=s[k-1][1][i];
            else{
                s[k][0][i]=char(((s[k-1][1][i]-'a')^(s[k-1][2][i]-'a'))+'a');
            }
            if(s[k-1][0][i]==s[k-1][2][i])
                s[k][1][i]=s[k-1][0][i];
            else{
                s[k][1][i]=char(((s[k-1][0][i]-'a')^(s[k-1][2][i]-'a'))+'a');
            }
            if(s[k-1][1][i]==s[k-1][0][i])
                s[k][2][i]=s[k-1][1][i];
            else{
                s[k][2][i]=char(((s[k-1][1][i]-'a')^(s[k-1][0][i]-'a'))+'a');
            }
        }
    }
    cin >> q >> t;
    bool fl=0;
    t='#'+t;
    change(t);
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)    
            if(s[i][j]==t)
                fl=1;
    if(fl)    cout << "Yes" << endl;
    else    cout << "No" << endl;
    while(q--){
        int l,r;
        char c;
        cin >> l >> r >> c;
        if(c=='J')    c='b';
        else if(c=='O')    c='c';
        else    c='d';
        for(int i=l;i<=r;i++)
            t[i]=c;
        fl=0;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                if(s[i][j]==t)
                    fl=1;
        if(fl)    cout << "Yes" << endl;
        else    cout << "No" << endl;
    }

    return 0;
}

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