Submission #1076543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076543		pcc	Rectangles (IOI19_rect)	C++17	100 / 100	2956 ms	811380 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#pragma GCC target("avx2,popcnt,sse4")
#pragma GCC optimize("O3,unroll-loops")
#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long
#define _all(T) T.begin(),T.end()
#define tiii tuple<int,int,int>

const int mxn = 2520;
int N,M;
vector<vector<int>> arr;
vector<pii> row[mxn][mxn],col[mxn][mxn];

struct BIT{
	int bit[mxn];
	void modify(int p,int v){
		p++;
		for(;p<mxn;p+=p&-p)bit[p] += v;
		return;
	}
	int getval(int s,int e = -1){
		s++,e++;
		if(s>e)swap(s,e);
		int re = 0;
		for(;e>0;e-= e&-e)re += bit[e];
		s--;
		for(;s>0;s-= s&-s)re -= bit[s];
		return re;
	}
};

BIT bit;
ll calc(vector<pii> &v1,vector<pii> &v2){
	vector<tiii> v;
	ll re = 0;
	for(auto &i:v1)if(i.sc != -1)v.push_back(tiii(i.fs,0,i.sc));
	for(auto &i:v2)if(i.sc != -1)v.push_back(tiii(i.sc,1,i.fs));
	sort(v.begin(),v.end());
	for(auto [_,tp,pos]:v){
		if(tp == 0)bit.modify(pos,1);
		else re += bit.getval(pos,mxn-1);
	}
	for(auto [_,tp,pos]:v){
		bit.modify(pos,-bit.getval(pos,pos));
	}
	return re;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	N = a.size(),M = a[0].size();
	arr = a;

	{
		for(int i = 0;i<N;i++){
			vector<int> st;
			vector<pii> rng(M,pii(-1,-1));
			for(int j = 0;j<M;j++){
				while(!st.empty()&&arr[i][j]>=arr[i][st.back()])st.pop_back();
				if(!st.empty())rng[j].fs = st.back();
				st.push_back(j);
			}
			st.clear();
			for(int j = M-1;j>=0;j--){
				while(!st.empty()&&arr[i][j]>=arr[i][st.back()])st.pop_back();
				if(!st.empty())rng[j].sc = st.back();
				st.push_back(j);
			}
			for(int j = 0;j<M;j++){
				if(rng[j].fs != -1&&rng[j].sc != -1){
					row[i][rng[j].fs+1].push_back(pii(rng[j].sc-1,-1));
				}
			}
			//cerr<<"ROW: "<<i<<":";for(auto &j:rng)cerr<<j.fs<<','<<j.sc<<' ';cerr<<endl;
		}
		for(int i = 0;i<M;i++){
			vector<int> st;
			vector<pii> rng(N,pii(-1,-1));
			for(int j = 0;j<N;j++){
				while(!st.empty()&&arr[st.back()][i]<=arr[j][i])st.pop_back();
				if(!st.empty())rng[j].fs = st.back();
				st.push_back(j);
			}
			st.clear();
			for(int j = N-1;j>=0;j--){
				while(!st.empty()&&arr[st.back()][i]<=arr[j][i])st.pop_back();
				if(!st.empty())rng[j].sc = st.back();
				st.push_back(j);
			}
			for(int j = 0;j<N;j++){
				if(rng[j].fs != -1&&rng[j].sc != -1){
					col[rng[j].fs+1][i].push_back(pii(rng[j].sc-1,-1));
				}
			}
			//cerr<<"COL: "<<i<<":";for(auto &j:rng)cerr<<j.fs<<','<<j.sc<<' ';cerr<<endl;
		}
	}

	for(int i = 0;i<N;i++)for(int j = 0;j<M;j++){
		sort(_all(row[i][j]));
		sort(_all(col[i][j]));
		row[i][j].resize(unique(_all(row[i][j]))-row[i][j].begin());
		col[i][j].resize(unique(_all(col[i][j]))-col[i][j].begin());
	}

	{
		int nxt[mxn] = {};
		for(int i = 0;i<M;i++){
			memset(nxt,-1,sizeof(nxt));
			for(int j = 0;j<N;j++){
				for(auto &[tar,rp]:row[j][i]){
					if(nxt[tar]<j)nxt[tar] = j;
					while(nxt[tar]+1<N){
						int tmp = nxt[tar]+1;
						auto it = lower_bound(_all(row[tmp][i]),pii(tar,-1));
						if(it == row[tmp][i].end()||it->fs != tar)break;
						nxt[tar]++;
					}
					rp = nxt[tar];
				}
			}
		}

		for(int i = 0;i<N;i++){
			memset(nxt,-1,sizeof(nxt));
			for(int j = 0;j<M;j++){
				for(auto &[tar,rp]:col[i][j]){
					if(nxt[tar]<j)nxt[tar] = j;
					while(nxt[tar]+1<M){
						int tmp =  nxt[tar]+1;
						auto it = lower_bound(_all(col[i][tmp]),pii(tar,-1));
						if(it == col[i][tmp].end()||it->fs != tar)break;
						nxt[tar]++;
					}
					rp = nxt[tar];
				}
			}
		}

	}

	ll ans = 0;
	{
		for(int i = 0;i<N;i++){
			for(int j = 0;j<M;j++){
				//cerr<<"CALC: "<<i<<','<<j<<endl;
				if(row[i][j].empty()||col[i][j].empty())continue;
				/*
				cerr<<"CALCING: "<<i<<','<<j<<endl;
				for(auto &k:row[i][j])cerr<<k.fs<<','<<k.sc<<' ';cerr<<endl;
				for(auto &k:col[i][j])cerr<<k.fs<<','<<k.sc<<' ';cerr<<endl;
				*/
				ans += calc(row[i][j],col[i][j]);
			}
		}
	}
	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: 28 / 28