oj.uz

Submission #1070390

# Submission time Handle Problem Language Result Execution time Memory
1070390 2024-08-22T13:51:34 Z j_vdd16 Rectangles (IOI19_rect) C++17
23 / 100
 3408 ms 208604 KB 
#include "rect.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define ll long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

long long count_rectangles(vvi a) {
	int n = a.size();
    int m = a[0].size();

    vector<set<ii>> validRows(n);
    for (int i = 1; i < n - 1; i++) {
        map<int, vi, greater<int>> values;
        loop(j, m) {
            values[a[i][j]].push_back(j);
        }

        map<int, int> rec;
        for (auto [val, vec] : values) {
            loop(idx, vec.size()) {
                if (rec.size() == 0) {
                    rec[vec[idx]] = val;
                    continue;
                }

                auto next = rec.upper_bound(vec[idx]);
                if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
                    validRows[i].insert({vec[idx], next->first});
                }

                next--;
                if (vec[idx] - next->first > 1)
                    validRows[i].insert({next->first, vec[idx]});

                rec[vec[idx]] = val;
            }
        }
    }
    vector<set<ii>> validCols(m);
    for (int j = 1; j < m - 1; j++) {
        map<int, vi, greater<int>> values;
        loop(i, n) {
            values[a[i][j]].push_back(i);
        }
        
        map<int, int> rec;
        for (auto [val, vec] : values) {
            loop(idx, vec.size()) {
                if (rec.size() == 0) {
                    rec[vec[idx]] = val;
                    continue;
                }

                auto next = rec.upper_bound(vec[idx]);
                if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
                    validCols[j].insert({vec[idx], next->first});
                }

                next--;
                if (vec[idx] - next->first > 1)
                    validCols[j].insert({next->first, vec[idx]});

                rec[vec[idx]] = val;
            }
        }
    }

    ll result = 0;
    for (int i = 1; i < n - 1; i++) {
        for (auto [x, y] : validRows[i]) {
            int furthest = i;
            while (validRows[furthest + 1].count({x, y})) furthest++;

            vi freq(furthest - i + 1);
            for (int j = x + 1; j <= y - 1; j++) {
                for (int i2 = i; i2 <= furthest; i2++) {
                    if (validCols[j].count({i - 1, i2 + 1}))
                        freq[i2 - i]++;
                }
            }

            ll extra = 0;
            for (int k = 0; k < furthest - i + 1; k++) {
                if (freq[k] == y - x - 1)
                    extra++;
            }

            result += extra;
        }
    }

    return result;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(vvi)':
rect.cpp:20:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
rect.cpp:47:13: note: in expansion of macro 'loop'
   47 |             loop(idx, vec.size()) {
      |             ^~~~
rect.cpp:54:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |                 if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
      |                                           ~~~~^~~~~~~~~~~~~~~~~
rect.cpp:20:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
rect.cpp:75:13: note: in expansion of macro 'loop'
   75 |             loop(idx, vec.size()) {
      |             ^~~~
rect.cpp:82:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |                 if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
      |                                           ~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 524 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 524 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 524 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 524 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1056 KB Output is correct
2 Correct 16 ms 876 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 5 ms 1112 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 4 ms 1196 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1490 ms 95904 KB Output is correct
3 Correct 3408 ms 207528 KB Output is correct
4 Correct 3263 ms 208468 KB Output is correct
5 Correct 3403 ms 208604 KB Output is correct
6 Correct 669 ms 30800 KB Output is correct
7 Correct 1233 ms 58276 KB Output is correct
8 Correct 1271 ms 62112 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 344 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 524 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -