Submission #697487

#	Time	Username	Problem	Language	Result	Execution time	Memory
697487		Sandarach151	Crossing (JOI21_crossing)	C++17	26 / 100	197 ms	7620 KiB

Main

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

struct segtree{
	vector<char> curequals;
	vector<char> targequals;
	vector<bool> equals;
	string cur;
	string targ;
	int size;
	segtree(int _size, string _cur, string _targ): cur(_cur), targ(_targ), size(_size){
        curequals.resize(4*size+5);
        targequals.resize(4*size+5);
        equals.resize(4*size+5);
        build(0, size-1, 0);
    }
    void build(int left, int right, int pos){
        if(left!=right){
            int mid = (left+right)/2;
            build(left, mid, 2*pos+1);
            build(mid+1, right, 2*pos+2);
            if(targequals[2*pos+1]==targequals[2*pos+2]){
                targequals[pos]=targequals[2*pos+1];
            }
            else{
                targequals[pos]='0';
            }
            if(curequals[2*pos+1]==curequals[2*pos+2]){
                curequals[pos]=curequals[2*pos+1];
            }
            else{
                curequals[pos]='0';
            }
            equals[pos]=(equals[2*pos+1] && equals[2*pos+2]);
        }
        else{
            targequals[pos] = targ[left];
            curequals[pos] = cur[left];
            equals[pos] = (targequals[pos]==curequals[pos]);
        }
    }
    void update(char c, int left, int right, int start, int end, int pos){
        if(start==left && end==right){
            curequals[pos] = c;
            equals[pos] = (targequals[pos]!='0' && curequals[pos]==targequals[pos]);
        }
        else{
            if(curequals[pos]!='0'){
                curequals[2*pos+1] = curequals[pos];
                equals[2*pos+1] = (targequals[2*pos+1]==curequals[2*pos+1]);
                curequals[2*pos+2] = curequals[pos];
                equals[2*pos+2] = (targequals[2*pos+2]==curequals[2*pos+2]);
                curequals[pos] = '0';
            }
            int mid = (left+right)/2;
            if(start>mid){
                update(c, mid+1, right, start, end, 2*pos+2);
            }
            else if(end<=mid){
                update(c, left, mid, start, end, 2*pos+1);
            }
            else{
                update(c, left, mid, start, mid, 2*pos+1);
                update(c, mid+1, right, mid+1, end, 2*pos+2);
            }
            equals[pos] = (equals[2*pos+2] && equals[2*pos+1]);
        }
    }
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    int n;
    cin >> n;
    string a, b, c;
    cin >> a >> b >> c;
    int q;
    cin >> q;
    string init;
    cin >> init;
    segtree root(n, init, a);
    if(root.equals[0]){
        cout << "Yes\n";
    }
    else{
        cout << "No\n";
    }
    for(int i=0; i<q; i++){
        int d, e;
        char f;
        cin >> d >> e >> f;
        d--;
        e--;
        root.update(f, 0, n-1, d, e, 0);
        if(root.equals[0]){
        cout << "Yes\n";
        }
        else{
            cout << "No\n";
        }
    }
    return 0;
}

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