Submission #1034423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034423		amirhoseinfar1385	Rectangles (IOI19_rect)	C++17	0 / 100	287 ms	593092 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=2500+10,ted=8;
long long all[maxn][maxn],vis[maxn][maxn],tp[maxn][maxn],n,m,dpp[maxn][maxn],dpd[maxn][maxn];
vector<long long>alll[maxn][maxn],alld[maxn][maxn];
vector<pair<long long,pair<long long,long long>>>allq[maxn][maxn];
vector<pair<long long,long long>>addy[maxn][maxn];
long long mainres=0;

struct fenwick{
	long long fn[maxn];
	vector<long long>allind;
	void clear(){
		for(auto x:allind){
			while(x<maxn){
				fn[x]=0;
				x+=((-x)&x);
			}
		}
		allind.clear();
	}
	void add(long long i,long long w){
		i++;
		allind.push_back(i);
		while(i<maxn){
			fn[i]+=w;
			i+=((-i)&i);
		}
	}
	long long pors(long long l,long long r){
		long long ret=0;
		r++;
		while(l>0){
			ret-=fn[l];
			l-=((-l)&l);
		}
		while(r>0){
			ret+=fn[r];
			r-=((-r)&r);
		}
		return ret;
	}
}fen;


void pre(){
	for(long long i=1;i<=n;i++){
		vector<pair<long long,long long>>allv;
		for(long long j=1;j<=m;j++){
			while((long long)allv.size()>0&&allv.back().first<all[i][j]){
				alll[i][j].push_back(allv.back().second);
				allv.pop_back();
			}
			if((long long)allv.size()>0){
				alll[i][j].push_back(allv.back().second);
			}
			allv.push_back(make_pair(all[i][j],j));
		}
	}
	for(long long j=1;j<=m;j++){
		vector<pair<long long,long long>>allv;
		for(long long i=n;i>=1;i--){
			while((long long)allv.size()>0&&allv.back().first<all[i][j]){
				alld[i][j].push_back(allv.back().second);
				allv.pop_back();
			}
			if((long long)allv.size()>0){
				alld[i][j].push_back(allv.back().second);
			}
			allv.push_back(make_pair(all[i][j],i));
		}
	}
}

void solveq(){
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			sort(addy[i][j].begin(),addy[i][j].end());
			sort(allq[i][j].begin(),allq[i][j].end());
	//		cout<<i<<" "<<j<<" :"<<endl;
	//		for(auto x:addy[i][j]){
	//			cout<<x.first<<" "<<x.second<<endl;
	//		}
	//		for(auto x:allq[i][j]){
	//			cout<<x.first<<" "<<x.second.first<<" "<<x.second.second<<endl;
	//		}
			while((long long)addy[i][j].size()>0&&(long long)allq[i][j].size()>0){
				if(addy[i][j].back().first>=allq[i][j].back().first){
					fen.add(addy[i][j].back().second,1);
					addy[i][j].pop_back();
				}else{
					mainres+=fen.pors(allq[i][j].back().second.first,allq[i][j].back().second.second);
					allq[i][j].pop_back();
				}
			}
			while((long long)allq[i][j].size()>0){
				mainres+=fen.pors(allq[i][j].back().second.first,allq[i][j].back().second.second);
				allq[i][j].pop_back();
			}
			fen.clear();
		}
	}
}

void calq(){
	for(long long i=0;i<=n;i++){
		for(long long j=1;j<=m;j++){
			for(auto x:alld[i][j]){
				if(x<=i+1){
					continue;
				}
				dpp[x][j]=dpp[x][j-1]+1;
				allq[i+1][j+1].push_back(make_pair((x-i-1),make_pair(j-dpp[x][j],j-1)));
			}
		}
		for(long long j=1;j<=m;j++){
			for(auto x:alld[i][j]){
				if(x<=i+1){
					continue;
				}
				dpp[x][j]=0;
			}
		}
	}
	for(long long j=1;j<=m;j++){
		for(long long i=n;i>=1;i--){
			for(auto x:alll[i][j]){
				if(x+1>=j){
					continue;
				}
				dpp[i][x]=dpp[i+1][x]+1;
				addy[i][j].push_back(make_pair(dpp[i][x],x));
			}
		}
		for(long long i=n;i>=1;i--){
			for(auto x:alll[i][j]){
				if(x+1>=j){
					continue;
				}
				dpp[i][x]=0;
			}
		}
	}
}

void solve(){
	pre();
	calq();
	solveq();
}
long long count_rectangles(std::vector<std::vector<int> > a) {
	n=a.size();
	m=a[0].size();
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			all[i][j]=a[i-1][j-1];
		}
	}
	solve();
	return mainres;
}

• 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