Submission #378722

#	Time	Username	Problem	Language	Result	Execution time	Memory
378722		autumn_eel	Rectangles (IOI19_rect)	C++14	27 / 100	5031 ms	796424 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

struct BIT{
	vector<int>bit;

	BIT(int n){
		bit=vector<int>(n+10);
	}

	void add(int k,int x){
		k++;
		while(k<bit.size()){
			bit[k]+=x;
			k+=k&-k;
		}
	}

	int sum(int k){
		k++;
		int res=0;
		while(k){
			res+=bit[k];
			k-=k&-k;
		}
		return res;
	}
};

struct st{
	int a,b,c;
};

static int r[3000][3000],l[3000][3000];
static int L[300][300][300],R[300][300][300];
static int M[300][300][300];

long long count_rectangles(std::vector<std::vector<int>> a) {
	int n=a.size(),m=a[0].size();
	rep(i,n){
		stack<P>sa;
		for(int j=m-1;j>=0;j--){
			while(!sa.empty()&&sa.top().first<a[i][j])sa.pop();
			r[i][j]=(sa.empty()?m:sa.top().second)-1;
			sa.push(P(a[i][j],j));
		}
		while(!sa.empty())sa.pop();
		rep(j,m){
			while(!sa.empty()&&sa.top().first<a[i][j])sa.pop();
			l[i][j]=(sa.empty()?-1:sa.top().second)+1;
			sa.push(P(a[i][j],j));
		}
	}
	rep(i,m){
		for(int j=0;j<n;j++){
			int r1=m-1;
			int l1=0;
			int m1=0;
			for(int k=j;k<n;k++){
				r1=min(r1,r[k][i]);
				R[i][j][k]=r1;
				l1=max(l1,l[k][i]);
				L[i][j][k]=l1;
				m1=max(m1,a[k][i]);
				M[i][j][k]=m1;
			}
		}
	}
	
	ll ans=0;
	for(int sx=0;sx<n;sx++){
		for(int gx=sx+2;gx<n;gx++){
			BIT bit(m);
			vector<st>v;
			int K=0;
			rep(j,m){
				int end=max(L[j][sx+1][gx-1]-1,K);
				if(end<=j-2){
					v.push_back({j-2,j,1});
					v.push_back({end-1,j,-1});
				}
				if(M[j][sx+1][gx-1]>=min(a[sx][j],a[gx][j])){
					K=j;
				}
			}
			sort(v.begin(),v.end(),[](st a,st b){return a.a>b.a;});
			//~ if(sx==0&&gx==3){
				//~ for(auto s:v){
					//~ cout<<s.a<<' '<<s.b<<' '<<s.c<<endl;
				//~ }
			//~ }
			int s=0;
			for(int j=m-1;j>=0;j--){
				while(s<v.size()&&v[s].a>=j){
					bit.add(v[s].b,v[s].c);
					s++;
				}
				ans+=bit.sum(R[j][sx+1][gx-1]+1);
			}
		}
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In member function 'void BIT::add(int, int)':
rect.cpp:17:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   while(k<bit.size()){
      |         ~^~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:98:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     while(s<v.size()&&v[s].a>=j){
      |           ~^~~~~~~~~

• 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