| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1054656 |
2024-08-12T11:24:12 Z |
dozer |
Rectangles (IOI19_rect) |
C++14 |
|
0 ms |
0 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 2505
#define LOGN 12
vector<pii> rng_h[MAXN], rng_v[MAXN];
vector<int> hor[MAXN][MAXN], ver[MAXN][MAXN];
vector<int> nxt_hor[MAXN][MAXN], nxt_ver[MAXN][MAXN];
void compute(vector<vector<int>> &a){
int n = a.size(), m = a.front().size();
for (int i = 1; i < n - 1; i++){
vector<int> nxt(m), prv(m);
nxt[m - 1] = m;
for (int j = m - 2; j >= 0; j--){
nxt[j] = j + 1;
while(nxt[j] < m && a[i][nxt[j]] < a[i][j]) nxt[j] = nxt[nxt[j]];
}
prv[0] = -1;
for (int j = 1; j < m; j++){
prv[j] = j - 1;
while(prv[j] != -1 && a[i][prv[j]] < a[i][j]) prv[j] = prv[prv[j]];
}
for (int j = 1; j < m - 1; j++)
if (prv[j] != -1 && nxt[j] != m && prv[j] < nxt[j] + 1) rng_h[i].pb({prv[j] + 1, nxt[j] - 1});
}
swap(n, m);
for (int i = 1; i < n - 1; i++){
vector<int> nxt(m), prv(m);
nxt[m - 1] = m;
for (int j = m - 2; j >= 0; j--){
nxt[j] = j + 1;
while(nxt[j] < m && a[nxt[j]][i] < a[j][i]) nxt[j] = nxt[nxt[j]];
}
prv[0] = -1;
for (int j = 1; j < m; j++){
prv[j] = j - 1;
while(prv[j] != -1 && a[prv[j]][i] < a[j][i]) prv[j] = prv[prv[j]];
}
for (int j = 1; j < m - 1; j++)
if (prv[j] != -1 && nxt[j] != m && prv[j] < nxt[j] + 1) rng_v[i].pb({prv[j] + 1, nxt[j] - 1});
}
}
int b_search(vector<int> &v, int pos){
int ans = pos;
for (int i = LOGN; i >= 0; i--){
int tmp = ans + (1<<i);
if (tmp >= v.size()) continue;
if (v[tmp] - v[pos] == tmp - pos) ans = tmp;
}
return ans;
}
int tree[MAXN];
void update(int x, int val, int n){
while(x <= n){
tree[x] += val;
x+=x&-x;
}
}
int query(int x){
int ans = 0;
while(x > 0) {
ans += tree[x];
x-=x&-x;
}
return ans;
}
long long count_rectangles(vector<vector<int>> a){
compute(a);
int n = a.size(), m = a.front().size();
for (int i = 1; i < n - 1; i++){
sort(rng_h[i].begin(), rng_h[i].end());
for (auto j : rng_h[i]){
hor[j.st][j.nd].pb(i);
}
}
for (int i = 1; i < m - 1; i++){
sort(rng_v[i].begin(), rng_v[i].end());
for (auto j : rng_v[i]){
ver[j.st][j.nd].pb(i);
}
}
long long ans = 0;
for (int i = 1; i < n - 1; i++){
for (int j = 1; j < m - 1; j++){
vector<pii> horr, verr;
int pos = lower_bound(rng_h[i].begin(), rng_h[i].end(), make_pair(j, 0)) - rng_h[i].begin();
while(pos != rng_h[i].size() && rng_h[i][pos].st == j){
int l = j, r = rng_h[i][pos].nd;
pos++;
int curr = lower_bound(hor[l][r].begin(), hor[l][r].end(), i) - hor[l][r].begin();
int to = hor[l][r][b_search(hor[l][r], curr)];
horr.pb({r, to});
}
pos = lower_bound(rng_v[j].begin(), rng_v[j].end(), make_pair(i, 0)) - rng_v[j].begin();
while(pos != rng_v[j].size() && rng_v[j][pos].st == i){
int l = i, r = rng_v[j][pos].nd;
pos++;
int curr = lower_bound(ver[l][r].begin(), ver[l][r].end(), j) - ver[l][r].begin();
int to = ver[l][r][b_search(ver[l][r], curr)];
verr.pb({to, r});
}
sort(horr.begin(), horr.end());
sort(verr.begin(), verr.end());
int it = 0;
vector<int> del;
for (auto k : verr){
while(it < horr.size() && horr[it].st <= k.st){
del.pb(horr[it].nd);
update(horr[it].nd, 1, n);
it++;
}
ans += query(n) - query(k.nd - 1);
}
for (auto i : del){
update(i, -1, n);
}
}
}
return ans;
return 0;
}
int main() {
fileio();
int n, m;
cin>>n>>m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin>>a[i][j];
}
}
long long result = count_rectangles(a);
printf("%lld\n", result);
return 0;
}
Compilation message
rect.cpp: In function 'int b_search(std::vector<int>&, int)':
rect.cpp:66:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | if (tmp >= v.size()) continue;
| ~~~~^~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:116:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | while(pos != rng_h[i].size() && rng_h[i][pos].st == j){
| ~~~~^~~~~~~~~~~~~~~~~~
rect.cpp:125:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | while(pos != rng_v[j].size() && rng_v[j][pos].st == i){
| ~~~~^~~~~~~~~~~~~~~~~~
rect.cpp:139:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | while(it < horr.size() && horr[it].st <= k.st){
| ~~~^~~~~~~~~~~~~
rect.cpp: In function 'int main()':
rect.cpp:10:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:160:2: note: in expansion of macro 'fileio'
160 | fileio();
| ^~~~~~
rect.cpp:10:59: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:160:2: note: in expansion of macro 'fileio'
160 | fileio();
| ^~~~~~
/usr/bin/ld: /tmp/ccgHV6M8.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cck40lL5.o:rect.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
