Submission #541652

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
541652	2022-03-24T01:59:29 Z	Olympia	Bob (COCI14_bob)	C++17	24 / 120	438 ms	14136 KB

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <limits.h>

using namespace std;

class Node {
public:
    int64_t left;
    int64_t right;
    int64_t tot;
    bool okay = true;
    Node (int x) {
        if (x == 0) {
            left = right = tot = 0;
        } else {
            left = right = tot = 1;
        }
    }
};

int64_t c2 (int64_t x) {
    return (x * (x + 1))/2;
}

Node merge (Node x, Node y) {
    if (!x.okay) return y;
    if (!y.okay) return x;
    Node ans(-1);
    bool full_x = (c2(x.left) == x.tot && x.tot != 0);
    bool full_y = (c2(y.left) == y.tot && y.tot != 0);
    ans.tot = x.tot + y.tot - c2(x.right) - c2(y.left) + c2(x.right + y.left);
    ans.left = x.left;
    ans.right = y.right;
    if (full_x) {
        ans.left += y.left;
    }
    if (full_y) {
        ans.right += x.right;
    }
    return ans;
}

class SegmentTree {
public:

    SegmentTree (int N) {
        N = (1 << ((int)floor(log2(N - 1)) + 1));
        this->N = N;
        val.assign(2 * N, Node(0));
    }

    void update (int x, Node y) {
        x += N - 1;
        val[x] = y;
        while (x != 0) {
            x = (x - 1)/2;
            val[x] = merge(val[2 * x + 1], val[2 * x + 2]);
            //cout << val[x].left << " " << val[2 * x + 1].left << " " << val[2 * x + 2].left << '\n';
        }
    }
    vector<Node> val;
private:
    int N;
};

int rectangle_count (vector<int> histogram) {
    SegmentTree st(histogram.size());
    vector<vector<int>> height;
    for (int i = 0; i < histogram.size(); i++) {
        st.update(i, Node(1));
        while (histogram[i] >= height.size()) {
            height.emplace_back();
        }
        height[histogram[i]].push_back(i);
    }
    int64_t ans = 0;
    for (int i = 0; i < height.size(); i++) {
        for (int j: height[i]) {
            //cout << "UPDATE " << j << '\n';
            st.update(j, Node(0));
        }
        ans += st.val[0].tot;
        //cout << st.val[0].tot << '\n';
    }
    //cout << '\n';
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    vector<vector<int>> arr(N);
    for (int i = 0; i < N; i++) {
        arr[i].resize(M);
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
    vector<int> his;
    his.assign(M, 1);
    int64_t ans = 0;
    for (int r = N - 1; r >= 0; r--) {
        for (int c = 0; c < M; c++) {
            his[c]--;
        }
        for (int c = 0; c < M; c++) {
            if (his[c] == 0) {
                int t = r;
                int cnt = 0;
                while (t >= 0 && arr[r][c] == arr[t][c]) {
                    t--;
                    cnt++;
                }
                his[c] = cnt;
            }
        }
        vector<vector<int>> h;
        for (int c = 0; c < M; c++) {
            if (c == 0 || arr[r][c] != arr[r][c - 1]) {
                h.push_back({his[c]});
            } else {
                h.back().push_back(his[c]);
            }
        }
        for (auto& vec: h)
        ans += rectangle_count(vec);
        /*
        for (auto& vec: h) {
            for (int i: vec) {
                cout << i << ' ';
            }
            cout << '\n';
        }
        cout << '\n';
         */
    }
    cout << ans;
}

Compilation message

bob.cpp: In function 'int rectangle_count(std::vector<int>)':
bob.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0; i < histogram.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
bob.cpp:80:29: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         while (histogram[i] >= height.size()) {
bob.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < height.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	472 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct

Subtask #3
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	90 ms	1940 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	107 ms	2348 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	94 ms	2528 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	98 ms	2524 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	403 ms	11132 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	414 ms	14136 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	433 ms	13944 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	438 ms	14028 KB	Output isn't correct
2	Halted	0 ms	0 KB	-