Submission #379116

#	Time	Username	Problem	Language	Result	Execution time	Memory
379116		Thistle	Rectangles (IOI19_rect)	C++14	0 / 100	20 ms	1644 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)]);
	}
};

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){
			 for(int t=j+2;t<ed;t++){
				if(!could[t]) continue;
				if(sph[k-1].get(j+1,t)>=a[k-1][t]){
					could[t]=0;
					continue;
				}
				if(spw[t-1].get(i+1,k)>=a[i][t-1]){
					ed=t;break;
				}
				if(spw[t-1].get(i+1,k)>=a[k][t-1])
					break;
				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 '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:43:3: note: in expansion of macro 'rep'
   43 |   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:44:3: note: in expansion of macro 'rep'
   44 |   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:46:4: note: in expansion of macro 'rep'
   46 |    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:50:3: note: in expansion of macro 'rep'
   50 |   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:50:13: note: in expansion of macro 'rep'
   50 |   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:53:4: note: in expansion of macro 'rng'
   53 |    rng(k,i+2,h){
      |    ^~~

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