Submission #1290694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290694		enzy	Rectangles (IOI19_rect)	C++20	27 / 100	5094 ms	77688 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=710;
set<int>col[maxn], lin[maxn];
int v[maxn][maxn], val[maxn][maxn], sp[maxn][maxn];
class SegTree{
protected:
	int seg[4*maxn];
public:
	void update(int id, int ini, int fim, int cara, int val){
		if(ini==fim){
			seg[id]=val;
			return;
		}
		int mid=(ini+fim)/2, e=2*id, d=2*id+1;
		if(cara<=mid) update(e,ini,mid,cara,val);
		else update(d,mid+1,fim,cara,val);
		seg[id]=max(seg[e],seg[d]);
	}
	int query(int id, int ini, int fim, int l, int r){
		if(ini>r||fim<l) return 0;
		if(l<=ini&&fim<=r) return seg[id];
		int mid=(ini+fim)/2, e=2*id, d=2*id+1;
		return max(query(e,ini,mid,l,r),query(d,mid+1,fim,l,r));
	}
};
SegTree seg_lin[maxn], seg_col[maxn];
ll count_rectangles(vector<vector<int> > a){
	int n=a.size(), m=a[0].size();
	vector<pair<int,pair<int,int>>>process;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			val[i+1][j+1]=a[i][j];
			col[j+1].insert(i+1);
			lin[i+1].insert(j+1);
			col[j+1].insert(0); col[j+1].insert(maxn);
			lin[i+1].insert(0); lin[i+1].insert(maxn);
			seg_lin[i+1].update(1,1,m,j+1,a[i][j]);
			seg_col[j+1].update(1,1,n,i+1,a[i][j]);
			process.push_back({a[i][j],{i+1,j+1}});
		}
	}
	sort(process.begin(),process.end()); reverse(process.begin(),process.end());
	ll resp=0;
	while(process.size()){
		set<pair<pair<int,int>,pair<int,int>>>ans;
		int at=process.back().first;
		vector<pair<int,int>>aux;
		vector<int>att;
		while(process.size()&&process.back().first==at){
			pair<int,int>p=process.back().second;
			aux.push_back(p);
			v[p.first][p.second]++;
			att.push_back(p.first);
			lin[p.first].erase(p.second); col[p.second].erase(p.first);
			process.pop_back();
		}
		for(int x : att)
			for(int i=1;i<=m;i++) sp[x][i]=sp[x][i-1]+v[x][i];
		for(pair<int,int> p : aux){
			int x=p.first, y=p.second;
			int l1, l2, c1, c2;
			auto f=lin[x].upper_bound(y), g=col[y].upper_bound(x);
			l2=*g; c2=*f;
		 	f--; g--;
			l1=*g; c1=*f;
			if(l1==0||c1==0||l2==maxn||c2==maxn) continue;
			l1++; c1++; l2--; c2--;
			bool ok=true;
			int qtd=c2-c1+1;
			for(int i=l1;i<=l2;i++) if(sp[i][c2]-sp[i][c1-1]!=qtd) ok=false;
			for(int i=l1;i<=l2;i++){
				int at=seg_lin[i].query(1,1,m,c1,c2);
				if(at>=min(val[i][c1-1],val[i][c2+1])) ok=false;
			}
			for(int i=c1;i<=c2;i++){
				int at=seg_col[i].query(1,1,n,l1,l2);
				if(at>=min(val[l1-1][i],val[l2+1][i])) ok=false;
			}
			if(ok) ans.insert({{l1,c1},{l2,c2}});
		}
		//for(pair<pair<int,int>,pair<int,int>> p : ans) cout << p.first.first << " " << p.first.second << " " << p.second.first << " " << p.second.second << endl;
		resp+=ans.size();
		/*for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++) cout << v[i][j] << " ";
			cout << endl;
		}
		cout << resp << endl << endl;*/
	}
	return resp;
}

• 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