Submission #378768

#	Time	Username	Problem	Language	Result	Execution time	Memory
378768		autumn_eel	Rectangles (IOI19_rect)	C++14	37 / 100	5113 ms	526560 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;
};

struct Segtree{
	int N;
	vector<int>dat;
	function<int(int,int)>f;
	int I;

	Segtree(){}
	Segtree(int n,int ini,function<int(int,int)>f):f(f),I(ini){
		N=1;while(N<n)N<<=1;
		dat=vector<int>(2*N,ini);
	}

	void update(int k,int x){
		k+=N;dat[k]=x;
		while(k>1){
			k>>=1;
			dat[k]=f(dat[k*2],dat[k*2+1]);
		}
	}

	int query(int l,int r){ // [l,r]
		r++;
		int res=I;
		for(l+=N,r+=N;l<r;l>>=1,r>>=1){
			if(l&1)res=f(res,dat[l++]);
			if(r&1)res=f(res,dat[--r]);
		}
		return res;
	}
};

struct SparseTable{
	vector<vector<int>>dat;
	vector<int>l2;
	function<int(int,int)>f;
	
	SparseTable(){}
	SparseTable(int n,function<int(int,int)>f):f(f){
		dat=vector<vector<int>>(13,vector<int>(n));
		l2=vector<int>(n+1);
		int s=1,x=0;
		for(int i=1;i<=n;i++){
			if(s*2<=i){
				s*=2;
				x++;
			}
			l2[i]=x;
		}
	}

	void init(){
		for(int i=0;i<12;i++){
			rep(j,dat[i].size()){
				if(j+(1<<i)>=dat[i].size())dat[i+1][j]=dat[i][j];
				else dat[i+1][j]=f(dat[i][j],dat[i][j+(1<<i)]);
			}
		}
	}

	int query(int l,int r){//[l,r]
		r++;
		int t=l2[r-l];
		return f(dat[t][l],dat[t][r-(1<<t)]); 
	}
};

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

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){
		R[i]=SparseTable(n,[](int a,int b){return min(a,b);});
		L[i]=SparseTable(n,[](int a,int b){return max(a,b);});
		M[i]=SparseTable(n,[](int a,int b){return max(a,b);});
	}

	rep(i,m){
		rep(j,n){
			R[i].dat[0][j]=r[j][i];
			L[i].dat[0][j]=l[j][i];
			M[i].dat[0][j]=a[j][i];
		}
		R[i].init();
		L[i].init();
		M[i].init();
	}
	
	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].query(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].query(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;});
			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].query(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 member function 'void SparseTable::init()':
rect.cpp:91:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     if(j+(1<<i)>=dat[i].size())dat[i+1][j]=dat[i][j];
      |        ~~~~~~~~^~~~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:160:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     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: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28