Submission #1048933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048933		fuad27	Rectangles (IOI19_rect)	C++17	100 / 100	2690 ms	902232 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
const int N = 2510;
int n,m;
vector<array<int, 2>> gdr[N][N];
vector<array<int, 2>> gdc[N][N];

struct Side {
	int r1, r2, c1, c2;
};


int fen[N];
void upd(int at, int add) {
	at++;
	while(at) {
		fen[at]+=add;
		at-=at&(-at);
	}
}
int qry(int at) {
	at++;
	int sum=0;
	while(at<N) {
		sum+=fen[at];
		at+=at&(-at);
	}
	return sum;
}
vector<int> stk;

long long count_rectangles(std::vector<std::vector<int> > a) {
	n = a.size();
	m = a[0].size();
	for(int i = 0;i<n;i++) {
			stk.clear();
		for(int j = 0;j<m;j++) {
			while(stk.size() and a[i][stk.back()] < a[i][j]){
				stk.pop_back();
			}
			if(stk.size()) {
				gdr[i][j].push_back({stk.back(), 1});
			}
			stk.push_back(j);
		}
		stk.clear();
		for(int j = m-1;j>=0;j--) {
			while(stk.size() and a[i][stk.back()] < a[i][j])stk.pop_back();
			if(stk.size()) {
				if(a[i][j] != a[i][stk.back()]) {
					gdr[i][stk.back()].push_back({j,1});
				}
			}
			stk.push_back(j);
		}
	}
	for(int i = 0;i<m;i++) {
			stk.clear();
		for(int j = 0;j<n;j++) {

			while(stk.size() and a[stk.back()][i] < a[j][i]){
				stk.pop_back();
			}
			if(stk.size()) {
				gdc[j][i].push_back({stk.back(),1});
			}
			stk.push_back(j);
		}
		stk.clear();
		for(int j = n-1;j>=0;j--) {
			while(stk.size() and a[stk.back()][i] < a[j][i])stk.pop_back();
			if(stk.size()) {
				if(a[j][i] != a[stk.back()][i]) {
					gdc[stk.back()][i].push_back({j, 1});
				}
			}
			stk.push_back(j);
		}
	}


	long long ans=0;
	for(int i = 0;i<n;i++) {
		for(int j = 0;j<m;j++) {
		sort(gdr[i][j].begin(), gdr[i][j].end());
		sort(gdc[i][j].begin(), gdc[i][j].end());
		gdr[i][j].erase(unique(gdr[i][j].begin(), gdr[i][j].end()), gdr[i][j].end());
		gdc[i][j].erase(unique(gdc[i][j].begin(), gdc[i][j].end()), gdc[i][j].end());
		if(i) {
				for(auto &[u, v]:gdr[i][j]) {
					auto it = lower_bound(gdr[i-1][j].begin(), gdr[i-1][j].end(), array<int,2>{u, 0});
					if(it!=gdr[i-1][j].end() and (*it)[0] == u) {
						v+=(*it)[1];
					}
				}
			}
			if(j) {
				for(auto &[u, v]:gdc[i][j]) {
					auto it = lower_bound(gdc[i][j-1].begin(), gdc[i][j-1].end(), array<int,2>{u, 0});
					if(it!=gdc[i][j-1].end() and (*it)[0] == u) {
						v+=(*it)[1];
					}
				}
			}
			if(i and j) {
				vector<pair<int,int>> A;
				vector<pair<int,int>> B;
				for(auto k:gdr[i-1][j]) {
					if(k[0]+1==j)continue;
					A.push_back(pair<int,int>(k[0], max(0, i-k[1]-1)));
				}
				for(auto k:gdc[i][j-1]) {
					if(k[0]+1 == i)continue;
					B.push_back(pair<int,int>(max(0, j-k[1]-1), k[0]));
				}
				sort(A.begin(),A.end());
				sort(B.begin(),B.end());
//				A[0] >= B[0]
//
//				B[1] >= A[1]
				int p1 = 0;
				for(auto k:A) {
					while(p1 < (int)B.size() and B[p1].first <= k.first) {
						upd(B[p1].second, 1);
						p1++;
					}
					ans+=qry(k.second);
				}
				while(p1 < B.size()) {
						upd(B[p1].second, 1);
						p1++;
				}
				for(auto k:B)upd(k.second, -1);
			}
		}
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:131:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     while(p1 < B.size()) {
      |           ~~~^~~~~~~~~~

• 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