Submission #697518

#	Time	Username	Problem	Language	Result	Execution time	Memory
697518		Sandarach151	Crossing (JOI21_crossing)	C++17	100 / 100	1930 ms	31384 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]);
        }
    }
};

char func2(char a, char b){
	if(a==b){
		return a;
	}
	else{
		if(a>b){
			swap(a, b);
		}
		if(a=='I' && b=='J'){
			return 'O';
		}
		else if(a=='I' && b=='O'){
			return 'J';
		}
		else{
			return 'I';
		}
	}
}

string func(string a, string b){
	string c = "";
	for(int i=0; i< (int) a.size(); i++){
		c+=" ";
		c[i]=func2(a[i], b[i]);
	}
	return c;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    int n;
    cin >> n;
    string a, b, c;
    cin >> a >> b >> c;
    set<string> vect;
    vect.insert(a);
    vect.insert(b);
    vect.insert(c);
    bool res = false;
    do{
        res = false;
        for(auto i : vect){
            for(auto u : vect){
                if(!vect.count(func(i, u))){
                    vect.insert(func(i, u));
                    res = true;
                }
            }
        }
    }
    while(res==true);
    vector<string> refarr;
    for(auto i : vect){
        refarr.push_back(i);
    }
    int q;
    cin >> q;
    string init;
    cin >> init;
    int num = refarr.size();
    vector<segtree> segs;
    for(int i=0; i<num; i++){
        segtree temp(n, init, refarr[i]);
        segs.push_back(temp);
    }
    bool curres = false;
    for(int i=0; i<num; i++){
        curres = curres || segs[i].equals[0];
    }
    curres ? cout << "Yes\n" : cout << "No\n";
    for(int i=0; i<q; i++){
        int d, e;
        char f;
        cin >> d >> e >> f;
        d--;
        e--;
        curres = false;
        for(int j=0; j<num; j++){
            segs[j].update(f, 0, n-1, d, e, 0);
            curres = curres || segs[j].equals[0];
        }
        curres ? cout << "Yes\n" : cout << "No\n";
    }
    return 0;
}

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