Submission #860084

#	Time	Username	Problem	Language	Result	Execution time	Memory
860084		sunwukong123	Rectangles (IOI19_rect)	C++14	72 / 100	5046 ms	1048576 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 2505;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 

int n,m;
long long ans;
struct fenw {
	int fw[MAXN];
	void update(int x, int nval){
		for(;x<MAXN;x+=x&-x)fw[x]+=nval;
	}
	int point(int x){
		int res=0;
		for(;x;x-=x&-x)res+=fw[x];
		return res;
	}
}fw;
vector<int> vxi[MAXN][MAXN];
vector<int> vyi[MAXN][MAXN];
vector<pi> H[MAXN][MAXN];
vector<pi> V[MAXN][MAXN];
struct hash_pair {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(pair<uint64_t,uint64_t> x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1);
    }
};

long long count_rectangles(std::vector<std::vector<int> > A) {
	n=A.size();
	m=A[0].size();
	for(int i=1;i<=n;i++){
		vector<pi> E;
		for(int j=1;j<=m;j++){
			E.push_back({A[i-1][j-1],j});
		}
		sort(E.begin(),E.end(),greater<pi>());
		
		set<int> s;
		vector<int> lazy;
		int pre=-1;
		unordered_set<pi,hash_pair> st;
		for(auto x:E){
			if(x.first!=pre){
				for(auto y:lazy){
					s.insert(y);
				}
				lazy.clear();
			}
			//debug(x.first,x.second);
			auto it=s.lower_bound(x.second);
			if(it == s.begin() || it==s.end());
			else {
				int L=*prev(it);
				int R=*it;
				st.insert({L+1,R-1});
				
			}
			lazy.push_back(x.second);
			pre=x.first;
		}
		for(auto x:st){
			int L=x.first;
			int R=x.second;
			vyi[L][R].push_back(i);
		}
	}

	for(int i=1;i<=m;i++){
		vector<pi> E;
		for(int j=1;j<=n;j++){
			E.push_back({A[j-1][i-1],j});
		}
		sort(E.begin(),E.end(),greater<pi>());
		set<int> s;
		vector<int> lazy;
		int pre=-1;
		unordered_set<pi,hash_pair> st;
		for(auto x:E){
			if(x.first!=pre){
				for(auto y:lazy){
					s.insert(y);
				}
				lazy.clear();
			}
			//debug(x.first,x.second);
			auto it=s.lower_bound(x.second);
			if(it == s.begin() || it==s.end());
			else {
				int L=*prev(it);
				int R=*it;
				//vxi[L][R].push_back(i);
				st.insert({L+1,R-1});
			}
			lazy.push_back(x.second);
			pre=x.first;
		}
		for(auto x:st){
			int L=x.first;
			int R=x.second;
			vxi[L][R].push_back(i);
		}
	}

	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			int st=0;

			for(int k=0;k<(int)vxi[i][j].size();k++){
				//debug(i,j,k,vxi[i][j][k]);
				int col=vxi[i][j][k];
				V[j][col].push_back({i,vxi[i][j][st]});
				
				if(k==((int)vxi[i][j].size()-1) || vxi[i][j][k]+1!=vxi[i][j][k+1]){

					st=k+1;
				} else{
				
				}
			}
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=i;j<=m;j++){
			int st=0;
			for(int k=0;k<(int)vyi[i][j].size();k++){
				int row=vyi[i][j][k];
				H[row][j].push_back({vyi[i][j][st],i});
				if(k==((int)vyi[i][j].size()-1) || vyi[i][j][k]+1!=vyi[i][j][k+1]){

					st=k+1;
				} else{
					
				}
			}
		}
	}

	for(int i=2;i<=n-1;i++){
		for(int j=2;j<=m-1;j++){
			// try this guy as the bottom right corner
			sort(H[i][j].begin(),H[i][j].end(),[](pi x, pi y) { return x.second>y.second; });
			sort(V[i][j].begin(),V[i][j].end(),[](pi x, pi y) { return x.second>y.second; });
			

			int idx=0;

			for(int k=0;k<(int)V[i][j].size();k++){
				while(idx<(int)H[i][j].size() && H[i][j][idx].second >= V[i][j][k].second) {
					fw.update(H[i][j][idx].first,1);
					++idx;
				}

				ans+=fw.point(V[i][j][k].first);
			}
			for(int k=0;k<idx;k++){
				fw.update(H[i][j][k].first,-1);
			}
		}
	}
	return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28