Submission #209922

#	Time	Username	Problem	Language	Result	Execution time	Memory
209922		Segtree	Rectangles (IOI19_rect)	C++14	27 / 100	2927 ms	126560 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 200
ll h,w,d[N][N];
namespace rangemax{
	ll dat1[N][N][N];//dat1[x][y1][y2]
	ll dat2[N][N][N];//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]);
				}
			}
		}
	}
};
bool solve(ll x1,ll x2,ll y1,ll y2){
	for(int x=x1;x<=x2;x++){
		if(rangemax::max_x(x,y1,y2)>=min(d[x][y1-1],d[x][y2+1]))return 0;
	}
	for(int y=y1;y<=y2;y++){
		if(rangemax::max_y(y,x1,x2)>=min(d[x1-1][y],d[x2+1][y]))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();
	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+=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: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28