Submission #1030934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030934		Dan4Life	Rectangles (IOI19_rect)	C++17	72 / 100	5079 ms	1044056 KiB

rect

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

#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

using ll = long long;
using vi = vector<int>;

const int mxN = 2502;
int n, m;
int pref[mxN][mxN], fen[mxN][mxN];
vector<int> row[mxN][mxN], col[mxN][mxN];
set<pair<int,int>> found[mxN][mxN];

struct Fenwick{
	int fen[mxN];
	void upd(int x, int v){
		for(++x; x<mxN; x+=x&-x) fen[x]+=v;
	}
	int sum(int x){
		int s = 0;
		for(++x; x>0; x-=x&-x) s+=fen[x];
		return s;
	}
	int sum(int l, int r){
		if(l>r)return 0;
		return sum(r)-sum(l-1);
	}
} fenc[mxN], fenr[mxN];

ll count_rectangles(vector<vi> a) {
	n = sz(a); m = sz(a[0]);
	ll ans = 0;
	for(int i = 0; i < n; i++){
		stack<int> S = stack<int>();
		for(int j = m-1; j >= 0; j--){
			while(sz(S) and a[i][S.top()]<a[i][j]) S.pop();
			if(sz(S) and abs(S.top()-j)>1){
				row[i][j].pb(S.top());
			}
			S.push(j);
		}
		S = stack<int>();
		for(int j = 0; j < m; j++){
			while(sz(S) and a[i][S.top()]<a[i][j]) S.pop();
			if(sz(S) and abs(S.top()-j)>1){
				if(a[i][S.top()]!=a[i][j]) 
					row[i][S.top()].pb(j);
			}
			S.push(j);
		}
	}
	for(int j = 0; j < m; j++){
		stack<int> S = stack<int>();
		for(int i = n-1; i >= 0; i--){
			while(sz(S) and a[S.top()][j]<a[i][j]) S.pop();
			if(sz(S) and abs(S.top()-i)>1){
				col[i][j].pb(S.top());
			}
			S.push(i);
		}
		S = stack<int>();
		for(int i = 0; i < n; i++){
			while(sz(S) and a[S.top()][j]<a[i][j]) S.pop();
			if(sz(S) and abs(S.top()-i)>1){
				if(a[S.top()][j]!=a[i][j])
					col[S.top()][j].pb(i);
			}
			S.push(i);
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			sort(all(row[i][j])),sort(all(col[i][j]));
			if(!sz(row[i][j])) continue;
		}
	}
	for(int i = 1; i < n-1; i++){
		for(int j = 0; j < m; j++)
			for(auto u : col[i-1][j]) fenc[u].upd(j,1);
		for(int j = 0; j < m; j++){
			int k = i;
			for(auto k : row[i][j]){
				int R = i+1;
				if(i>1 and binary_search(all(row[i-1][j]),k)){
					R = found[i-1][j].lower_bound({k,-1})->second;
				}
				else{
					while(R<n and binary_search(all(row[R][j]),k)) R++;
				}
				found[i][j].insert({k,R});

			    for(auto l : col[i-1][j+1]){
					if(fenc[l].sum(j+1,k-1)!=k-j-1) continue;
					if(l>R) break; ans++;
				}
			}
			for(auto u : col[i-1][j]) fenc[u].upd(j,-1);
		}
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:98:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   98 |      if(l>R) break; ans++;
      |      ^~
rect.cpp:98:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   98 |      if(l>R) break; ans++;
      |                     ^~~
rect.cpp:85:8: warning: unused variable 'k' [-Wunused-variable]
   85 |    int k = i;
      |        ^

• 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