제출 #379144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379144		Thistle	Rectangles (IOI19_rect)	C++14	25 / 100	5087 ms	590700 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()%4+1;
	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]);
	 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;
}

컴파일 시 표준 에러 (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()%4+1;
      |  ^~~
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()%4+1;
      |          ^~~
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) 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:79:3: note: in expansion of macro 'rep'
   79 |   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:81:4: note: in expansion of macro 'rep'
   81 |    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:85:3: note: in expansion of macro 'rep'
   85 |   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:85:13: note: in expansion of macro 'rep'
   85 |   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:88:4: note: in expansion of macro 'rng'
   88 |    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: 0 / 13
• Subtask 7: 0 / 28