oj.uz

Submission #697475

# Submission time Handle Problem Language Result Execution time Memory
697475 2023-02-10T02:44:52 Z Sandarach151 Crossing (JOI21_crossing) C++17
3 / 100
 7000 ms 19552 KB 
#include <bits/stdc++.h>
using namespace std;

string cur, targ;

struct node{
    node *l, *r;
    int start, mid, end;
    char curequals, targequals;
    bool equals;
    node(int _start, int _end, string _cur, string _targ): start(_start), mid((_start+_end)/2), end(_end){
        if(start!=end){
            l = new node(start, mid, cur, targ);
            r = new node(mid+1, end, cur, targ);
            if(l->targequals==r->targequals){
                this->targequals=l->targequals;
            }
            else{
                this->targequals='0';
            }
            if(l->curequals==r->curequals){
                this->curequals=l->curequals;
            }
            else{
                this->curequals='0';
            }
            this->equals=(l->equals && r->equals);
        }
        else{
            this->targequals = targ[start];
            this->curequals = cur[start];
            this->equals = (this->targequals==this->curequals);
        }
    }
    void update(char c, int left, int right){
        if(start==left && end==right){
            this->curequals = c;
            this->equals = (this->targequals!='0' && this->curequals==this->targequals);
        }
        else{
            if(this->curequals!='0'){
                l->curequals = this->curequals;
                l->equals = (l->targequals==l->curequals);
                r->curequals = this->curequals;
                r->equals = (r->targequals==r->curequals);
                this->curequals = '0';
            }
            if(left>mid){
                r->update(c, left, right);
            }
            else if(right<=mid){
                l->update(c, left, right);
            }
            else{
                l->update(c, left, mid);
                r->update(c, mid+1, right);
            }
            this->equals = (r->equals && l->equals);
        }
    }
};

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;
    cur = init;
    targ = a;
    node root(0, n-1, init, a);
    if(root.equals){
        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, d, e);
        if(root.equals){
        cout << "Yes\n";
        }
        else{
            cout << "No\n";
        }
    }
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 940 KB Output is correct
2 Correct 54 ms 940 KB Output is correct
3 Correct 56 ms 996 KB Output is correct
4 Correct 48 ms 908 KB Output is correct
5 Correct 52 ms 2296 KB Output is correct
6 Correct 63 ms 2256 KB Output is correct
7 Correct 49 ms 2376 KB Output is correct
8 Correct 52 ms 2424 KB Output is correct
9 Correct 53 ms 2404 KB Output is correct
10 Correct 49 ms 2380 KB Output is correct
11 Correct 51 ms 2344 KB Output is correct
12 Correct 49 ms 2340 KB Output is correct
13 Correct 50 ms 2384 KB Output is correct
14 Correct 49 ms 2360 KB Output is correct
15 Correct 60 ms 2368 KB Output is correct
16 Correct 56 ms 2400 KB Output is correct
17 Correct 54 ms 2376 KB Output is correct
18 Correct 51 ms 2340 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 940 KB Output is correct
2 Correct 54 ms 940 KB Output is correct
3 Correct 56 ms 996 KB Output is correct
4 Correct 48 ms 908 KB Output is correct
5 Correct 52 ms 2296 KB Output is correct
6 Correct 63 ms 2256 KB Output is correct
7 Correct 49 ms 2376 KB Output is correct
8 Correct 52 ms 2424 KB Output is correct
9 Correct 53 ms 2404 KB Output is correct
10 Correct 49 ms 2380 KB Output is correct
11 Correct 51 ms 2344 KB Output is correct
12 Correct 49 ms 2340 KB Output is correct
13 Correct 50 ms 2384 KB Output is correct
14 Correct 49 ms 2360 KB Output is correct
15 Correct 60 ms 2368 KB Output is correct
16 Correct 56 ms 2400 KB Output is correct
17 Correct 54 ms 2376 KB Output is correct
18 Correct 51 ms 2340 KB Output is correct
19 Execution timed out 7068 ms 19552 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 940 KB Output is correct
2 Correct 54 ms 940 KB Output is correct
3 Correct 56 ms 996 KB Output is correct
4 Correct 48 ms 908 KB Output is correct
5 Correct 52 ms 2296 KB Output is correct
6 Correct 63 ms 2256 KB Output is correct
7 Correct 49 ms 2376 KB Output is correct
8 Correct 52 ms 2424 KB Output is correct
9 Correct 53 ms 2404 KB Output is correct
10 Correct 49 ms 2380 KB Output is correct
11 Correct 51 ms 2344 KB Output is correct
12 Correct 49 ms 2340 KB Output is correct
13 Correct 50 ms 2384 KB Output is correct
14 Correct 49 ms 2360 KB Output is correct
15 Correct 60 ms 2368 KB Output is correct
16 Correct 56 ms 2400 KB Output is correct
17 Correct 54 ms 2376 KB Output is correct
18 Correct 51 ms 2340 KB Output is correct
19 Correct 52 ms 844 KB Output is correct
20 Correct 53 ms 840 KB Output is correct
21 Incorrect 51 ms 820 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 940 KB Output is correct
2 Correct 54 ms 940 KB Output is correct
3 Correct 56 ms 996 KB Output is correct
4 Correct 48 ms 908 KB Output is correct
5 Correct 52 ms 2296 KB Output is correct
6 Correct 63 ms 2256 KB Output is correct
7 Correct 49 ms 2376 KB Output is correct
8 Correct 52 ms 2424 KB Output is correct
9 Correct 53 ms 2404 KB Output is correct
10 Correct 49 ms 2380 KB Output is correct
11 Correct 51 ms 2344 KB Output is correct
12 Correct 49 ms 2340 KB Output is correct
13 Correct 50 ms 2384 KB Output is correct
14 Correct 49 ms 2360 KB Output is correct
15 Correct 60 ms 2368 KB Output is correct
16 Correct 56 ms 2400 KB Output is correct
17 Correct 54 ms 2376 KB Output is correct
18 Correct 51 ms 2340 KB Output is correct
19 Execution timed out 7068 ms 19552 KB Time limit exceeded
20 Halted 0 ms 0 KB -