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++) {
      |                     ~~^~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 472 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 1940 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 2348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 2528 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 2524 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 403 ms 11132 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 414 ms 14136 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 433 ms 13944 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 438 ms 14028 KB Output isn't correct
2 Halted 0 ms 0 KB -