| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 541659 |
2022-03-24T02:18:19 Z |
Olympia |
Bob (COCI14_bob) |
C++17 |
|
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++) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
1384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
1396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
1376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
1340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
