Submission #529588

#	Time	Username	Problem	Language	Result	Execution time	Memory
529588		c28dnv9q3	Crossing (JOI21_crossing)	C++17	100 / 100	2424 ms	28068 KiB

Main

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

#pragma GCC optimize "O3"

#define _strfy(s) #s
#define strfy(s) _strfy(s)

#define ALPHABET "JOI"

#define MAX_N 200000
int seq_len;
char seqA[MAX_N+1], seqB[MAX_N+1], seqC[MAX_N+1];
char seqAB[MAX_N+1], seqBC[MAX_N+1], seqAC[MAX_N+1];
char seqABC[MAX_N+1], seqBCA[MAX_N+1], seqACB[MAX_N+1];
char seqT[MAX_N+1];

#define MAX_Q 200000
int num_mods;
struct mod {
    int left, right;
    char chr;
} mods[MAX_Q];
bool posbl[MAX_Q+1];

static inline void validate(const char *seq) {
    assert(strlen(seq) == seq_len);
    for(; *seq != 0; seq++) assert(*seq == ALPHABET[0] || *seq == ALPHABET[1] || *seq == ALPHABET[2]);
}

static inline void cross(const char *seq1, const char *seq2, char *seqO) {
    for(int i = 0; i < seq_len; i++) {
        if(seq1[i] == seq2[i]) seqO[i] = seq1[i];
        else if(seq1[i] == ALPHABET[1] && seq2[i] == ALPHABET[2]) seqO[i] = ALPHABET[0];
        else if(seq1[i] == ALPHABET[2] && seq2[i] == ALPHABET[1]) seqO[i] = ALPHABET[0];
        else if(seq1[i] == ALPHABET[0] && seq2[i] == ALPHABET[2]) seqO[i] = ALPHABET[1];
        else if(seq1[i] == ALPHABET[2] && seq2[i] == ALPHABET[0]) seqO[i] = ALPHABET[1];
        else if(seq1[i] == ALPHABET[0] && seq2[i] == ALPHABET[1]) seqO[i] = ALPHABET[2];
        else if(seq1[i] == ALPHABET[1] && seq2[i] == ALPHABET[0]) seqO[i] = ALPHABET[2];
        else assert(false);
    }
}

struct node {
    struct node *lchild, *rchild;
    int left, right;

    int lazy_c;

    int numA, numB, numC;
    int numM; //numMatch
} nodes[2*MAX_N], *next_node;

struct node *create_tree(const char *seq, int l = -1, int r = -1) {
    if(l < 0 && r < 0) {
        next_node = nodes;
        l = 0;
        r = seq_len;
    }

    assert(0 <= l && l < r && r <= seq_len);
    assert(next_node < nodes + 2*MAX_N);

    struct node *node = next_node++;
    node->left = l;
    node->right = r;
    node->lazy_c = -1;

    if(l == r - 1) {
        node->lchild = NULL;
        node->rchild = NULL;
        node->numA = (seq[l] == ALPHABET[0]) ? 1 : 0;
        node->numB = (seq[l] == ALPHABET[1]) ? 1 : 0;
        node->numC = (seq[l] == ALPHABET[2]) ? 1 : 0;
        node->numM = (seq[l] == seqT[l]) ? 1 : 0;
    } else {
        int m = l + (r - l) / 2;
        node->lchild = create_tree(seq, l, m);
        node->rchild = create_tree(seq, m, r);
        node->numA = node->lchild->numA + node->rchild->numA;
        node->numB = node->lchild->numB + node->rchild->numB;
        node->numC = node->lchild->numC + node->rchild->numC;
        node->numM = node->lchild->numM + node->rchild->numM;
    }

    return node;
}

void update_lazy(struct node *node) {
    if(node->lazy_c < 0) return;

    switch(node->lazy_c) {
        case(ALPHABET[0]): { node->numM = node->numA; } break;
        case(ALPHABET[1]): { node->numM = node->numB; } break;
        case(ALPHABET[2]): { node->numM = node->numC; } break;
        default: assert(false);
    }

    if(node->lchild != NULL) node->lchild->lazy_c = node->lazy_c;
    if(node->rchild != NULL) node->rchild->lazy_c = node->lazy_c;

    node->lazy_c = -1;
}

void update_tree(struct node *node, int l, int r, char c) {
    update_lazy(node);

    assert(0 <= l && l < r && r <= seq_len);
    assert(0 <= node->left && node->left < node->right && node->right <= seq_len);
    
    if(r <= node->left || node->right <= l) return;

    if(l <= node->left && node->right <= r) {
        node->lazy_c = c;
        update_lazy(node);
        return;
    }

    assert(node->lchild != NULL && node->rchild != NULL);
    update_tree(node->lchild, l, r, c);
    update_tree(node->rchild, l, r, c);
    node->numM = node->lchild->numM + node->rchild->numM;
}

void check_seq(const char *seq) {
    struct node *tree = create_tree(seq);

    for(int m = -1; m < num_mods; m++) {
        if(m >= 0) update_tree(tree, mods[m].left, mods[m].right, mods[m].chr);

        assert(0 <= tree->numM && tree->numM <= seq_len);
        posbl[m+1] = posbl[m+1] || tree->numM == seq_len;
    }
}

int main() {
    assert(scanf("%d", &seq_len) == 1);
    assert(1 <= seq_len && seq_len <= MAX_N);

    assert(scanf("%" strfy(MAX_N) "s", seqA) == 1);
    validate(seqA);
    assert(scanf("%" strfy(MAX_N) "s", seqB) == 1);
    validate(seqB);
    assert(scanf("%" strfy(MAX_N) "s", seqC) == 1);
    validate(seqC);

    cross(seqA, seqB, seqAB);
    cross(seqB, seqC, seqBC);
    cross(seqA, seqC, seqAC);

    cross(seqAB, seqC, seqABC);
    cross(seqBC, seqA, seqBCA);
    cross(seqAC, seqB, seqACB);

    assert(scanf("%d", &num_mods) == 1);
    assert(1 <= num_mods && num_mods <= MAX_Q);

    assert(scanf("%" strfy(MAX_N) "s", seqT) == 1);
    validate(seqT);

    posbl[0] = false;
    for(int m = 0; m < num_mods; m++) {
        int l, r;
        char c;
        assert(scanf("%d %d %c", &l, &r, &c) == 3);
        assert(1 <= l && l <= r && r <= seq_len);
        assert(c == ALPHABET[0] || c == ALPHABET[1] || c == ALPHABET[2]);

        mods[m].left = l-1;
        mods[m].right = r;
        mods[m].chr = c;
        posbl[m+1] = false;
    }

    check_seq(seqA);
    check_seq(seqB);
    check_seq(seqC);

    check_seq(seqAB);
    check_seq(seqBC);
    check_seq(seqAC);

    check_seq(seqABC);
    check_seq(seqBCA);
    check_seq(seqACB);

    for(int m = 0; m <= num_mods; m++) {
        if(posbl[m]) puts("Yes");
        else puts("No");
    }

    return EXIT_SUCCESS;
}

Compilation message (stderr)

In file included from Main.cpp:4:
Main.cpp: In function 'void validate(const char*)':
Main.cpp:29:24: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     assert(strlen(seq) == seq_len);
      |            ~~~~~~~~~~~~^~~~~~~~~~

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