Submission #209944

#	Time	Username	Problem	Language	Result	Execution time	Memory
209944		Segtree	Rectangles (IOI19_rect)	C++14	0 / 100	550 ms	256076 KiB

rect

#include"rect.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unordered_set<ll> uset;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=0;i<=n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")
#define N 2500
ll h,w,d[N][N];
ll rui[N][N];
ll qry(ll x1,ll x2,ll y1,ll y2){//全て0のとき0、1のとき1、混在しているとき2
	x2++,y2++;
	ll res=rui[x2][y2]+rui[x1][y1]-rui[x2][y1]-rui[x1][y2];
	if(res==0)return 0;
	if(res==(x2-x1)*(y2-y1))return 1;
	return 2;
}
ll nx[N][N],ny[N][N];
ll count_rectangles(vector<vector<int> >A){
	h=A.size(),w=A[0].size();
	rep(i,h)rep(j,w)d[i][j]=A[i][j];
	rep(i,h+1)rep(j,w+1)rui[i][j]=0;
	rep(i,h)rep(j,w)rui[i+1][j+1]=A[i][j];
	rep(i,h+1)rep(j,w){
		rui[i][j+1]+=rui[i][j];
	}
	rep(j,w+1)rep(i,h){
		rui[i+1][j]+=rui[i][j];
	}
	rep(i,h+1)rep(j,w+1)nx[i][j]=ny[i][j]=1e9;
	rep(i,h){
		for(int j=w-1;j>=0;j--)nx[i][j]=(A[i][j]==1?j:nx[i][j+1]);
	}
	rep(j,w){
		for(int i=h-1;i>=0;i--)ny[i][j]=(A[i][j]==1?i:ny[i+1][j]);
	}
	ll ans=0;
	for(int i=1;i<h-1;i++)for(int j=1;j<w-1;j++){
		if(A[i][j]==1)continue;
		int x1=i,x2=ny[i][j]-1; if(x2>h-2)continue;
		int y1=j,y2=nx[i][j]-1; if(y2>w-2)continue;
		//cerr<<x1<<" "<<x2<<" "<<y1<<" "<<y2<<endl;
		bool ok=qry(x1,x2,y1,y2)==0;
		ok&=qry(x1-1,x1-1,y1,y2)==1;
		ok&=qry(x2+1,x2+1,y1,y2)==1;
		ok&=qry(x1,x2,y1-1,y1-1)==1;
		ok&=qry(x1,x2,y2+1,y2+1)==1;
		ans+=ok;
	}
	return ans;
}/*
int main(){
	ll h,w;
	cin>>h>>w;
	vector<vector<int> >a(h);
	rep(i,h){
		rep(j,w){
			ll val;cin>>val;
			a[i].push_back(val);
		}
	}
	cout<<count_rectangles(a)<<endl;
}*/

Compilation message (stderr)

rect.cpp:17:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("O3")
 
rect.cpp:18:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("unroll-loops")
 
rect.cpp:19:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
 #pragma gcc target("avx2,see4")

• 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