답안 #541659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541659	2022-03-24T02:18:19 Z	Olympia	Bob (COCI14_bob)	C++17	120 / 120	478 ms	6424 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 is_full = true;
    Node (int x) {
        if (x == 0) {
            left = right = tot = 0;
            is_full = false;
        } else {
            left = right = tot = 1;
        }
    }
};

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

Node merge (Node x, Node y) {
    Node ans(-1);
    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 (x.is_full) {
        ans.left += y.left;
    }
    if (y.is_full) {
        ans.right += x.right;
    }
    ans.is_full = (x.is_full && y.is_full);
    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]);
        }
    }
    vector<Node> val;
private:
    int N;
};

int64_t rectangle_count (vector<int64_t> histogram) {
    SegmentTree st(histogram.size());
    vector<vector<int64_t>> 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);
    }
    vector<int> v;
    v.assign(histogram.size(), 1);
    int64_t ans = 0;
    for (int i = 0; i < height.size(); i++) {
        for (int64_t j: height[i]) {
            st.update(j, Node(0));
            v[j] = 0;
        }
        ans += st.val[0].tot;
        //ans += st.val[0].tot;
    }
    return ans;
}
int main() {
//    freopen("inp.txt", "r", stdin);
    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<int64_t> 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<int64_t>> 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);
        }
    }
    cout << ans;
}

Compilation message

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

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	94 ms	1384 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	99 ms	1396 KB	Output is correct

Subtask #5
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	98 ms	1376 KB	Output is correct

Subtask #6
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	116 ms	1340 KB	Output is correct

Subtask #7
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	389 ms	4368 KB	Output is correct
2	Correct	450 ms	6384 KB	Output is correct
3	Correct	472 ms	6352 KB	Output is correct

Subtask #8
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	411 ms	4364 KB	Output is correct
2	Correct	434 ms	6416 KB	Output is correct
3	Correct	478 ms	6348 KB	Output is correct

Subtask #9
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	427 ms	4432 KB	Output is correct
2	Correct	455 ms	6352 KB	Output is correct
3	Correct	461 ms	6424 KB	Output is correct

Subtask #10
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	445 ms	4496 KB	Output is correct
2	Correct	452 ms	6384 KB	Output is correct
3	Correct	471 ms	6340 KB	Output is correct