Maalaus

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <stdint.h>
#include <unordered_map>
#include <unordered_set>
 
uint64_t *colors;
 
size_t width;
size_t height;
size_t color_count;
 
size_t get_uuid(int32_t rc, size_t n) {
    return ((size_t)rc << 32) | n;
}
 
struct DrawData {
    int32_t color;
    size_t covered;
};
 
std::unordered_map<size_t, DrawData> row_ops;
std::unordered_map<size_t, DrawData> col_ops;
 
std::unordered_map<size_t, std::unordered_set<size_t>> ops_covered;
 
void insert_op(int rc, size_t n, int color) {
    if (rc == 'R') {
        row_ops[get_uuid(rc, n)] = {color, width};
    } else {
        col_ops[get_uuid(rc, n)] = {color, height};
    }
}
 
void draw_line(int rc, size_t n, int color) {
    if (row_ops.size() == 0 and col_ops.size() == 0) {
        insert_op(rc, n, color);
        return;
    }
    
    if (rc == 'R') {
        const auto same_line = row_ops.find(get_uuid(rc, n));
        if (same_line != row_ops.end()) {
            same_line->second.covered = 0;
        }
 
        for (auto &r : col_ops) {
            const auto same_line_covered = same_line != row_ops.end() ? ops_covered.find(same_line->first) : ops_covered.end();
            // For when we re-draw a line that has been covered by a new orthogonal line
            const auto opp_line_covered = same_line != row_ops.end() ? ops_covered.find(r.first) : ops_covered.end();
            if (opp_line_covered != ops_covered.end() and opp_line_covered->second.find(get_uuid(rc, n)) != opp_line_covered->second.end()) {
                opp_line_covered->second.erase(opp_line_covered->second.find(get_uuid(rc, n)));
            }
 
 
            if (same_line_covered != ops_covered.end()) {
                if (same_line_covered->second.find(r.first) == same_line_covered->second.end()) {
                    r.second.covered--;
                } else {
                    same_line_covered->second.erase(same_line_covered->second.find(r.first));
                }
            } else {
                r.second.covered--;
            }

            ops_covered[get_uuid(rc, n)].insert(r.first);
        }
 
    } else {
        const auto same_line = col_ops.find(get_uuid(rc, n));
        if (same_line != col_ops.end()) {
            same_line->second.covered = 0;
        }
 
        for (auto &r : row_ops) {
            const auto same_line_covered = same_line != col_ops.end() ? ops_covered.find(same_line->first) : ops_covered.end();
            // For when we re-draw a line that has been covered by a new orthogonal line
            const auto opp_line_covered = same_line != col_ops.end() ? ops_covered.find(r.first) : ops_covered.end();
            if (opp_line_covered != ops_covered.end() and opp_line_covered->second.find(get_uuid(rc, n)) != opp_line_covered->second.end()) {
                opp_line_covered->second.erase(opp_line_covered->second.find(get_uuid(rc, n)));
            }
 
 
            if (same_line_covered != ops_covered.end()) {
                if (same_line_covered->second.find(r.first) == same_line_covered->second.end()) {
                    r.second.covered--;
                } else {
                    same_line_covered->second.erase(same_line_covered->second.find(r.first));
                }
            } else {
                r.second.covered--;
            }

            ops_covered[get_uuid(rc, n)].insert(r.first);
        }
 
    }
 
    insert_op(rc, n, color);
}
 
 
int main(void) {
    char *input = (char *)malloc(1024*1024*8);
    const size_t len = read(0, input, 1024*1024*8);
    size_t idx = 0;
 
    size_t next_space = strchr(input, ' ') - input;
    input[next_space] = '\0';
    height = atoi(input);
    idx += next_space + 1;
 
    next_space = strchr((input + idx), ' ') - (input + idx);
    (input + idx)[next_space] = '\0';
    width = atoi((input + idx));
    idx += next_space + 1;
 
    next_space = strchr((input + idx), ' ') - (input + idx);
    (input + idx)[next_space] = '\0';
    color_count = atoi((input + idx));
    idx += next_space + 1;
 
    next_space = strchr((input + idx), '\n') - (input + idx);
    (input + idx)[next_space] = '\0';
    size_t operations = atoi((input + idx));
    idx += next_space + 1;
 
    colors = (uint64_t *)malloc((color_count + 1) * sizeof(uint64_t));
    row_ops.reserve(operations);
    col_ops.reserve(operations);
    ops_covered.reserve(operations);
 
    for (size_t i = 0; i < color_count + 1; i++) {
        colors[i] = 0;
    }
 
    for (size_t i = 0; i < operations; i++) {
        int rc = (input + idx)[0];
        idx += 2;
 
        next_space = strchr((input + idx), ' ') - (input + idx);
        (input + idx)[next_space] = '\0';
        size_t n = atoi((input + idx));
        idx += next_space + 1;
 
        if (i == operations - 1) {
            next_space = len - ((input + idx) - input) - 1;
        } else {
            next_space = strchr((input + idx), '\n') - (input + idx);
        }
 
        (input + idx)[next_space] = '\0';
        size_t color = atoi((input + idx));
        idx += next_space + 1;
 
        draw_line(rc, n, color);
    }
 
    for (auto &r : row_ops) {
        colors[r.second.color] += r.second.covered;
        printf("%lu\n", r.second.covered);
    }
 
    for (auto &r : col_ops) {
        colors[r.second.color] += r.second.covered;
    }
 
    for (size_t i = 1; i < color_count + 1; i++) {
        printf("%lu ", colors[i]);
    }
 
    free(input);
    free(colors);
 
}

Test 1 (public)

Group: 1, 3, 4

Verdict: WRONG ANSWER

Test 2 (public)

Group: 3, 4

Verdict: WRONG ANSWER

Test 3

Group: 1, 3, 4

Verdict: WRONG ANSWER

Test 4

Group: 2, 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 2, 4

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 3, 4

Verdict: WRONG ANSWER

Test 7

Group: 3, 4

Verdict: WRONG ANSWER

Test 8

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 3, 4

Verdict: WRONG ANSWER

Test 11

Group: 1, 3, 4

Verdict: WRONG ANSWER

Test 12

Group: 2, 4

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 2, 4

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 4

Verdict: TIME LIMIT EXCEEDED