oj.uz

Submission #619886

# Submission time Handle Problem Language Result Execution time Memory
619886 2022-08-02T16:51:35 Z APROHACK Crossing (JOI21_crossing) C++14
0 / 100
 382 ms 1136 KB 
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
string a, b, c, x;
ll n, q;
struct crossing
{
    ll dd, ht, mid;
    char toProp;
    bool faltaprop;
    bool allJ, allO, allI, iscorrect;
    crossing *L, *R;
    crossing(){}
    crossing(int l, int r){
        dd = l, ht = r;
        mid = (dd+ht)/2;
        if(l!=r){
            L = new crossing(l, mid);
            R = new crossing(mid+1, r);
            allJ = L->allJ && R->allJ;
            allO = L->allO && R->allO;
            allI = L->allI && R->allI;
            iscorrect = L->iscorrect && R->iscorrect;
        }else{
            allJ = a[dd] == 'J';
            allO = a[dd] == 'O';
            allI = a[dd] == 'I';
            if(a[dd]==x[dd])iscorrect = true;
        }
    }
    void propagate(){
        if(!faltaprop)return;
        L->insert(dd, mid, toProp);
        R->insert(mid+1, ht, toProp);
        iscorrect = L->iscorrect && R->iscorrect;
        faltaprop=false;
    }
    void insert(int l, int r, char cual){
        if(dd == l && r==ht ){
            if(cual == 'J' && allJ)iscorrect = true;
            else if(cual == 'O'&&allO)iscorrect=true;
            else if(cual == 'I' && allI)iscorrect = true;
            else iscorrect=false;
            if(dd != ht)propagate();
            //no hace falta propagar lo que hay aca
            toProp = cual;
            faltaprop = true;
            return ;
        }
        propagate();
        if(r<=mid)L->insert(l, r, cual);
        else if(mid<l)R->insert(l, r, cual);
        else {
            L->insert(l, mid, cual);
            R->insert(mid+1, r, cual);
        }
        iscorrect = L->iscorrect && R->iscorrect;
    }
 
};
crossing *seg;
void input(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
    cin>>n;
    cin>>a>>b>>c;
    cin>>q;
    cin>>x;
}
bool askforX(){
    seg = new crossing(0, n-1);
    return seg->iscorrect;
}
int main(){
    input();
    if(askforX())cout << "Yes\n";
    else cout << "No\n";
    ll l, r;
    char value;
    for(int i = 0 ; i < q ; i++){
        cin>>l>>r>>value;
        seg->insert(l-1, r-1, value);
        if(seg->iscorrect)cout<<"Yes\n";
        else cout << "No\n";
    }
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 968 KB Output is correct
2 Correct 149 ms 1064 KB Output is correct
3 Correct 382 ms 1136 KB Output is correct
4 Incorrect 109 ms 1076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 968 KB Output is correct
2 Correct 149 ms 1064 KB Output is correct
3 Correct 382 ms 1136 KB Output is correct
4 Incorrect 109 ms 1076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 968 KB Output is correct
2 Correct 149 ms 1064 KB Output is correct
3 Correct 382 ms 1136 KB Output is correct
4 Incorrect 109 ms 1076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 968 KB Output is correct
2 Correct 149 ms 1064 KB Output is correct
3 Correct 382 ms 1136 KB Output is correct
4 Incorrect 109 ms 1076 KB Output isn't correct
5 Halted 0 ms 0 KB -