This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "rect.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_set>
using namespace std;
typedef long long ll;
const int maxn=2503, Log=12, pot=(1<<Log);
const int inf=1e9;
ll sol;
int svi[maxn][maxn][4];
int n, m;
unordered_set < ll > bio;
int svi1[maxn][maxn][4];
struct tmin{
int t[pot*2];
void update(int x, int val){
t[x]=val;
}
void gradi(){
for(int x=pot-1; x>0; x--){
t[x]=min(t[x*2], t[x*2+1]);
}
}
int query(int l, int r){
int sol=inf;
for(l+=pot, r+=pot; l<r; l>>=1, r>>=1){
if(l&1){
sol=min(sol, t[l++]);
}
if(r&1){
sol=min(sol, t[--r]);
}
}
return sol;
}
};
struct tmax{
int t[pot*2];
void update(int x, int val){
t[x]=val;
}
void gradi(){
for(int x=pot-1; x>0; x--){
t[x]=max(t[x*2], t[x*2+1]);
}
}
int query(int l, int r){
int sol=0;
for(l+=pot, r+=pot; l<r; l>>=1, r>>=1){
if(l&1){
sol=max(sol, t[l++]);
}
if(r&1){
sol=max(sol, t[--r]);
}
}
return sol;
}
};
tmin R1[maxn], C1[maxn];
tmax R2[maxn], C2[maxn];
ll count_rectangles(vector < vector < int > > a){
n=a.size();
m=a[0].size();
vector < pair <int, int > > v;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
while(!v.empty() && v.back().first<a[i][j]){
v.pop_back();
}
if(v.empty()){
svi1[i][j][2]=0;
}
else{
svi1[i][j][2]=v.back().second+1;
}
while(!v.empty() && v.back().first<=a[i][j]){
v.pop_back();
}
if(v.empty()){
svi[i][j][2]=0;
}
else{
svi[i][j][2]=v.back().second+1;
}
v.push_back({a[i][j], j});
}
v.clear();
for(int j=m-1; j>-1; j--){
while(!v.empty() && v.back().first<a[i][j]){
v.pop_back();
}
if(v.empty()){
svi1[i][j][3]=m-1;
}
else{
svi1[i][j][3]=v.back().second-1;
}
while(!v.empty() && v.back().first<=a[i][j]){
v.pop_back();
}
if(v.empty()){
svi[i][j][3]=m-1;
}
else{
svi[i][j][3]=v.back().second-1;
}
v.push_back({a[i][j], j});
}
v.clear();
}
for(int j=0; j<m; j++){
for(int i=0; i<n; i++){
while(!v.empty() && v.back().first<a[i][j]){
v.pop_back();
}
if(v.empty()){
svi1[i][j][0]=0;
}
else{
svi1[i][j][0]=v.back().second+1;
}
while(!v.empty() && v.back().first<=a[i][j]){
v.pop_back();
}
if(v.empty()){
svi[i][j][0]=0;
}
else{
svi[i][j][0]=v.back().second+1;
}
v.push_back({a[i][j], i});
}
v.clear();
for(int i=n-1; i>-1; i--){
while(!v.empty() && v.back().first<a[i][j]){
v.pop_back();
}
if(v.empty()){
svi1[i][j][1]=n-1;
}
else{
svi1[i][j][1]=v.back().second-1;
}
while(!v.empty() && v.back().first<=a[i][j]){
v.pop_back();
}
if(v.empty()){
svi[i][j][1]=n-1;
}
else{
svi[i][j][1]=v.back().second-1;
}
v.push_back({a[i][j], i});
}
v.clear();
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
R1[i].update(j+pot, svi1[i][j][1]);
R2[i].update(j+pot, svi1[i][j][0]);
C1[j].update(i+pot, svi1[i][j][3]);
C2[j].update(i+pot, svi1[i][j][2]);
}
}
for(int i=0; i<n; i++){
R1[i].gradi();
R2[i].gradi();
}
for(int i=0; i<m; i++){
C1[i].gradi();
C2[i].gradi();
}
int c[4];
ll br;
int sz;
for(int i=1; i<n-1; i++){
for(int j=1; j<m-1; j++){
br=0;
for(int k=0; k<4; k++){
c[k]=svi[i][j][k];
br*=maxn;
br+=c[k];
}
if(c[0]==0 || c[2]==0 || c[1]==n-1 || c[3]==m-1){
continue;
}
if(c[0]<R2[c[1]+1].query(c[2], c[3]+1)){
continue;
}
if(c[1]>R1[c[0]-1].query(c[2], c[3]+1)){
continue;
}
if(c[2]<C2[c[3]+1].query(c[0], c[1]+1)){
continue;
}
if(c[3]>C1[c[2]-1].query(c[0], c[1]+1)){
continue;
}
sz=bio.size();
bio.insert(br);
if(sz==bio.size()){
continue;
}
// cout << c[0] << ' '<< c[2] << ' ' << c[1] << ' ' << c[3] << endl;
sol++;
}
}
return sol;
}
Compilation message (stderr)
rect.cpp:1: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
1 | #pragma comment(linker, "/stack:200000000")
|
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
from /usr/include/c++/10/ext/atomicity.h:35,
from /usr/include/c++/10/bits/ios_base.h:39,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from rect.cpp:6:
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:226:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_set<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
226 | if(sz==bio.size()){
| ~~^~~~~~~~~~~~