Submission #1242906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242906		AMnu	Rectangles (IOI19_rect)	C++20	100 / 100	1463 ms	610600 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN = 2505;

int N, M, fen[MAXN];
ll ans;
pii B[MAXN][MAXN];
vector <pii> C[2][MAXN][MAXN];

int pref(int x) {
	int sum = 0;
	for (int i=x;i;i-=i&-i) {
		sum += fen[i];
	}
	return sum;
}

void add(int x,int y) {
	for (int i=x;i<MAXN;i+=i&-i) {
		fen[i] += y;
	}
}

void reset() {
	for (int i=0;i<MAXN;i++) {
		for (int j=i+2;j<MAXN;j++) {
			B[i][j] = {-1,-1};
		}
	}
}

void get(int i,int x,int y,int t) {
	if (y-x == 1) return;
	if (B[x][y].se == i-1) {
		B[x][y].se++;
	}
	else {
		B[x][y] = {i,i};
	}
	C[t][i][y-1].push_back({x+1,B[x][y].fi});
}

void solve(int x,int y) {
	vector <pii> &A = C[0][x][y];
	vector <pii> &B = C[1][y][x];
	for (pii &x : B) {
		swap(x.fi,x.se);
	}
	sort(A.begin(),A.end());
	sort(B.begin(),B.end());
	int j=0;
	for (int i=0;i<(int)A.size();i++) {
		while (j<(int)B.size() && B[j].fi<=A[i].fi) {
			add(B[j].se,1);
			j++;
		}
		ans += j-pref(A[i].se-1);
	}
	for (int i=0;i<j;i++) {
		add(B[i].se,-1);
	}
}

ll count_rectangles(vector<vector<int> > A) {
	N = A.size();
	M = A[0].size();
	reset();
	for (int i=1;i<N-1;i++) {
		stack <pii> S;
		for (int j=0;j<M;j++) {
			while (!S.empty() && S.top().fi < A[i][j]) {
				get(i,S.top().se,j,0);
				S.pop();
			}
			if (!S.empty()) {
				get(i,S.top().se,j,0);
				if (S.top().fi == A[i][j]) {
					S.pop();
				}
			}
			S.push({A[i][j],j});
		}
	}
	reset();
	for (int i=1;i<M-1;i++) {
		stack <pii> S;
		for (int j=0;j<N;j++) {
			while (!S.empty() && S.top().fi < A[j][i]) {
				get(i,S.top().se,j,1);
				S.pop();
			}
			if (!S.empty()) {
				get(i,S.top().se,j,1);
				if (S.top().fi == A[j][i]) {
					S.pop();
				}
			}
			S.push({A[j][i],j});
		}
	}
	for (int i=1;i<N-1;i++) {
		for (int j=1;j<M-1;j++) {
			if (!C[0][i][j].empty() && !C[1][j][i].empty()) {
				solve(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