oj.uz

Submission #697471

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

struct node{
    node *l, *r;
    int start, mid, end;
    char curequals, targequals;
    bool equals;
    string cur;
    string targ;
    node(int _start, int _end, string _cur, string _targ): start(_start), mid((_start+_end)/2), end(_end), cur(_cur), targ(_targ){
        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(){
    int n;
    cin >> n;
    string a, b, c;
    cin >> a >> b >> c;
    int q;
    cin >> q;
    string init;
    cin >> init;
    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 309 ms 844 KB Output is correct
2 Correct 381 ms 920 KB Output is correct
3 Correct 330 ms 896 KB Output is correct
4 Correct 317 ms 924 KB Output is correct
5 Correct 355 ms 2312 KB Output is correct
6 Correct 311 ms 2336 KB Output is correct
7 Correct 346 ms 2408 KB Output is correct
8 Correct 356 ms 2368 KB Output is correct
9 Correct 345 ms 2428 KB Output is correct
10 Correct 342 ms 2432 KB Output is correct
11 Correct 343 ms 2464 KB Output is correct
12 Correct 333 ms 2396 KB Output is correct
13 Correct 333 ms 2556 KB Output is correct
14 Correct 334 ms 2488 KB Output is correct
15 Correct 338 ms 2380 KB Output is correct
16 Correct 338 ms 2392 KB Output is correct
17 Correct 347 ms 2420 KB Output is correct
18 Correct 333 ms 2352 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 844 KB Output is correct
2 Correct 381 ms 920 KB Output is correct
3 Correct 330 ms 896 KB Output is correct
4 Correct 317 ms 924 KB Output is correct
5 Correct 355 ms 2312 KB Output is correct
6 Correct 311 ms 2336 KB Output is correct
7 Correct 346 ms 2408 KB Output is correct
8 Correct 356 ms 2368 KB Output is correct
9 Correct 345 ms 2428 KB Output is correct
10 Correct 342 ms 2432 KB Output is correct
11 Correct 343 ms 2464 KB Output is correct
12 Correct 333 ms 2396 KB Output is correct
13 Correct 333 ms 2556 KB Output is correct
14 Correct 334 ms 2488 KB Output is correct
15 Correct 338 ms 2380 KB Output is correct
16 Correct 338 ms 2392 KB Output is correct
17 Correct 347 ms 2420 KB Output is correct
18 Correct 333 ms 2352 KB Output is correct
19 Runtime error 518 ms 1048576 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 844 KB Output is correct
2 Correct 381 ms 920 KB Output is correct
3 Correct 330 ms 896 KB Output is correct
4 Correct 317 ms 924 KB Output is correct
5 Correct 355 ms 2312 KB Output is correct
6 Correct 311 ms 2336 KB Output is correct
7 Correct 346 ms 2408 KB Output is correct
8 Correct 356 ms 2368 KB Output is correct
9 Correct 345 ms 2428 KB Output is correct
10 Correct 342 ms 2432 KB Output is correct
11 Correct 343 ms 2464 KB Output is correct
12 Correct 333 ms 2396 KB Output is correct
13 Correct 333 ms 2556 KB Output is correct
14 Correct 334 ms 2488 KB Output is correct
15 Correct 338 ms 2380 KB Output is correct
16 Correct 338 ms 2392 KB Output is correct
17 Correct 347 ms 2420 KB Output is correct
18 Correct 333 ms 2352 KB Output is correct
19 Correct 344 ms 2360 KB Output is correct
20 Correct 412 ms 2264 KB Output is correct
21 Incorrect 333 ms 2456 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 844 KB Output is correct
2 Correct 381 ms 920 KB Output is correct
3 Correct 330 ms 896 KB Output is correct
4 Correct 317 ms 924 KB Output is correct
5 Correct 355 ms 2312 KB Output is correct
6 Correct 311 ms 2336 KB Output is correct
7 Correct 346 ms 2408 KB Output is correct
8 Correct 356 ms 2368 KB Output is correct
9 Correct 345 ms 2428 KB Output is correct
10 Correct 342 ms 2432 KB Output is correct
11 Correct 343 ms 2464 KB Output is correct
12 Correct 333 ms 2396 KB Output is correct
13 Correct 333 ms 2556 KB Output is correct
14 Correct 334 ms 2488 KB Output is correct
15 Correct 338 ms 2380 KB Output is correct
16 Correct 338 ms 2392 KB Output is correct
17 Correct 347 ms 2420 KB Output is correct
18 Correct 333 ms 2352 KB Output is correct
19 Runtime error 518 ms 1048576 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -