Submission #209933

#	Time	Username	Problem	Language	Result	Execution time	Memory
209933		Segtree	Rectangles (IOI19_rect)	C++14	10 / 100	93 ms	121860 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
#define H 3
int h,w,d[N][N];
namespace rangemax{
	int dat1[H][N][N];//dat1[x][y1][y2]
	int dat2[N][H][H];//dat2[y][x1][x2]
	ll max_x(ll x,ll y1,ll y2){
		return dat1[x][y1][y2];
	}
	ll max_y(ll y,ll x1,ll x2){
		return dat2[y][x1][x2];
	}
	void init(){
		rep(i,h){
			rep(l,w){
				dat1[i][l][l]=d[i][l];
				for(int r=l+1;r<w;r++){
					dat1[i][l][r]=max(dat1[i][l][r-1],d[i][r]);
				}
			}
		}
		rep(i,w){
			rep(l,h){
				dat2[i][l][l]=d[l][i];
				for(int r=l+1;r<h;r++){
					dat2[i][l][r]=max(dat2[i][l][r-1],d[r][i]);
				}
			}
		}
	}
};
namespace rangejudge{
	int dat1[H][N][N];//dat1[x][y1][y2]
	int dat2[N][H][H];//dat2[y][x1][x2]
	void init(){
		rep(i,h){
			for(int l=0;l<w;l++)for(int r=l;r<w;r++){
				dat1[i][l][r]=rangemax::max_x(i,l,r)>=min(d[i][l-1],d[i][r+1]);
			}
		}
		for(int l=0;l<w;l++)for(int r=l;r<w;r++){
			for(int i=1;i<h;i++)dat1[i][l][r]+=dat1[i-1][l][r];
		}
		rep(i,w){
			for(int l=0;l<h;l++)for(int r=l;r<h;r++){
				dat2[i][l][r]=rangemax::max_y(i,l,r)>=min(d[l-1][i],d[r+1][i]);
			}
		}
		for(int l=0;l<h;l++)for(int r=l;r<h;r++){
			for(int i=1;i<w;i++)dat2[i][l][r]+=dat2[i-1][l][r];
		}
	}
	bool solve(ll x1,ll x2,ll y1,ll y2){
		if(dat1[x2][y1][y2]-dat1[x1-1][y1][y2]>0)return 0;
		if(dat2[y2][x1][x2]-dat2[y1-1][x1][x2]>0)return 0;
		return 1;
	}
};
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];
	rangemax::init();
	rangejudge::init();
	ll ans=0;
	for(int x1=1;x1<h-1;x1++)for(int x2=x1;x2<h-1;x2++)
	for(int y1=1;y1<w-1;y1++)for(int y2=y1;y2<w-1;y2++){
		ans+=rangejudge::solve(x1,x2,y1,y2);
	}
	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: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28