Submission #379148

#	Time	Username	Problem	Language	Result	Execution time	Memory
379148		Thistle	Rectangles (IOI19_rect)	C++14	38 / 100	5057 ms	49516 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using H=pair<ll, ll>;
using vi=vector<ll>;
#define vec vector
#define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),(0),(n))
#define fs first
#define sc second
#define all(a) (a).begin(),(a).end()
#define siz(a) ll((a).size())

class sptable{
	int n;
	vi lgt;
	vec<vi> dat;
public:
	sptable(vec<int> v){
		n=siz(v);
		lgt.assign(n+1,0);
		for(int i=2;i<=n;i++) lgt[i]=lgt[i>>1]+1;
		dat.assign(lgt[n]+1,vi(n));
		rep(i,n) dat[0][i]=v[i];
		rng(i,0,lgt[n]){
			for(int j=0;j+(1<<(i+1))<=n;j++){
				dat[i+1][j]=max(dat[i][j],dat[i][j+(1<<i)]);
			}
		}
	}
	sptable(){}
	ll get(int l,int r){
		int k=lgt[r-l];
		return max(dat[k][l],dat[k][r-(1<<k)]);
	}
};
mt19937 rnd;
vec<vec<int>>vv;
ll gen(){
	int n=rnd()%4+3,m=rnd()%4+3;
	vec<vec<int>>v(n,vec<int>(m));
	rep(i,n)rep(j,m) v[i][j]=rnd()%2;
	ll ans=0;
	rep(i,n-2)rep(j,m-2){
		rng(k,i+2,n)rng(t,j+2,m){
			bool flag=1;
			rng(x,i+1,k)rng(y,j+1,t){
				if(v[x][y]>=min({v[i][y],v[k][y],v[x][j],v[x][t]})) flag=0;
			}
			if(flag) ans++;
		}
	}
	vv=v;
	return ans;
}
void check(){
	rep(i,1000){
		ll ans=gen();
		ll sol=count_rectangles(vv);
		if(ans!=sol){
			cout<<siz(vv)<<" "<<siz(vv[0])<<endl;
			for(auto g:vv){
				for(auto t:g)cout<<t<<" ";
				cout<<endl;
			}
			cout<<ans<<" "<<sol<<endl;
			break;
		}
		cout<<i<<endl;
	}
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	 int h=siz(a),w=siz(a[0]);
	 int mxv=0;
	 rep(i,h)rep(j,w) mxv=max(mxv,a[i][j]);
	 if(mxv<=1){
	 ll ans=0;
	 rep(i,h)rep(j,w){
		 if(a[i][j]==1) continue;
		 queue<H>q;
		 q.push(H{i,j});
		 int inf=10000;
		 ll mnx=inf,mxx=-inf,mny=inf,mxy=-inf;
		 vi dx={-1,1,0,0},dy={0,0,-1,1};
		 a[i][j]=1;
		 int sum=0;
		 while(!q.empty()){
			 H t=q.front();q.pop();
			 mnx=min(mnx,t.fs);
			 mxx=max(mxx,t.fs);
			 mny=min(mny,t.sc);
			 mxy=max(mxy,t.sc);
			 sum++;
			 rep(z,4){
				 H k=H{t.fs+dx[z],t.sc+dy[z]};
				 if(k.fs<0||k.fs>=h||k.sc<0||k.sc>=w) continue;
				 if(a[k.fs][k.sc]==0){
					 q.push(k);
					 a[k.fs][k.sc]=1;
				 }
			 }
		 }
		 if(mnx==0||mny==0||mxx==h-1||mxy==w-1) continue;
		 if(sum==(mxx-mnx+1)*(mxy-mny+1)){
			 ans++;
		 }
	 }
	 return ans;
	 }
	 else{
		 vec<sptable>sph(h),spw(w);
		 rep(i,h) sph[i]=sptable(a[i]);
		 rep(j,w){
			 vec<int>v(h);
			 rep(i,h) v[i]=a[i][j];
			 spw[j]=sptable(v);
		 }
		 ll ans=0;
		 rep(i,h-2)rep(j,w-2){
			 vec<bool>could(w,1);
			 int ed=w;
			 rng(k,i+2,h){
				 bool flag=0;
				 for(int t=j+2;t<ed;t++){
					int r=0;
					if(!could[t]) r=1;
					if(sph[k-1].get(j+1,t)>=a[k-1][t]){
						could[t]=0;
						r=1;
					}
					if(sph[k-1].get(j+1,t)>=a[k-1][j]){
						ed=t;
						r=1;
					}
					if(spw[t-1].get(i+1,k)>=a[i][t-1]){
						ed=t;r=2;
					}
					if(spw[t-1].get(i+1,k)>=a[k][t-1])
						r=1,flag=1;
					if(r==2) break;
					if(r==1||flag) continue;
					ans++;
				 }
			 }
		 }
		 return ans;
	 }
}

Compilation message (stderr)

rect.cpp: In constructor 'sptable::sptable(std::vector<int>)':
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:26:3: note: in expansion of macro 'rep'
   26 |   rep(i,n) dat[0][i]=v[i];
      |   ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:27:3: note: in expansion of macro 'rng'
   27 |   rng(i,0,lgt[n]){
      |   ^~~
rect.cpp: In function 'll gen()':
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:44:2: note: in expansion of macro 'rep'
   44 |  rep(i,n)rep(j,m) v[i][j]=rnd()%2;
      |  ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:44:10: note: in expansion of macro 'rep'
   44 |  rep(i,n)rep(j,m) v[i][j]=rnd()%2;
      |          ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:46:2: note: in expansion of macro 'rep'
   46 |  rep(i,n-2)rep(j,m-2){
      |  ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:46:12: note: in expansion of macro 'rep'
   46 |  rep(i,n-2)rep(j,m-2){
      |            ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:47:3: note: in expansion of macro 'rng'
   47 |   rng(k,i+2,n)rng(t,j+2,m){
      |   ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 't' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:47:15: note: in expansion of macro 'rng'
   47 |   rng(k,i+2,n)rng(t,j+2,m){
      |               ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:49:4: note: in expansion of macro 'rng'
   49 |    rng(x,i+1,k)rng(y,j+1,t){
      |    ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'y' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:49:16: note: in expansion of macro 'rng'
   49 |    rng(x,i+1,k)rng(y,j+1,t){
      |                ^~~
rect.cpp: In function 'void check()':
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:59:2: note: in expansion of macro 'rep'
   59 |  rep(i,1000){
      |  ^~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:78:3: note: in expansion of macro 'rep'
   78 |   rep(i,h)rep(j,w) mxv=max(mxv,a[i][j]);
      |   ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:78:11: note: in expansion of macro 'rep'
   78 |   rep(i,h)rep(j,w) mxv=max(mxv,a[i][j]);
      |           ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:81:3: note: in expansion of macro 'rep'
   81 |   rep(i,h)rep(j,w){
      |   ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:81:11: note: in expansion of macro 'rep'
   81 |   rep(i,h)rep(j,w){
      |           ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:97:5: note: in expansion of macro 'rep'
   97 |     rep(z,4){
      |     ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:115:4: note: in expansion of macro 'rep'
  115 |    rep(i,h) sph[i]=sptable(a[i]);
      |    ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:116:4: note: in expansion of macro 'rep'
  116 |    rep(j,w){
      |    ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:118:5: note: in expansion of macro 'rep'
  118 |     rep(i,h) v[i]=a[i][j];
      |     ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:122:4: note: in expansion of macro 'rep'
  122 |    rep(i,h-2)rep(j,w-2){
      |    ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:10:18: note: in expansion of macro 'rng'
   10 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
rect.cpp:122:14: note: in expansion of macro 'rep'
  122 |    rep(i,h-2)rep(j,w-2){
      |              ^~~
rect.cpp:9:28: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
    9 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
rect.cpp:125:5: note: in expansion of macro 'rng'
  125 |     rng(k,i+2,h){
      |     ^~~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28