Submission #954708

#	Time	Username	Problem	Language	Result	Execution time	Memory
954708		waldi	Rectangles (IOI19_rect)	C++17	72 / 100	5107 ms	504256 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

ll count_rectangles(vector<vector<int>> wej){
	int n = ssize(wej);
	int m = ssize(wej[0]);
	if(n<3 || m<3) return 0ll;
	
	vector poziomo(m, vector(m, vector<int>()));
	FOR(i, 1, n-2){
		vector<int> stos;
		REP(j, m){
			while(ssize(stos) && wej[i][stos.back()] < wej[i][j]){
				int t = stos.back();
				if(t+1 <= j-1) poziomo[t+1][j-1].emplace_back(i);
				stos.pop_back();
			}
			if(ssize(stos)){
				int t = stos.back();
				if(t+1 <= j-1) poziomo[t+1][j-1].emplace_back(i);
				if(wej[i][t] == wej[i][j]) stos.pop_back();
			}
			stos.emplace_back(j);
		}
	}
	
	//~ vector pionowo(n, vector(n, vector<int>()));
	vector pionowo(n, vector(m, vector<int>()));
	FOR(i, 1, m-2){
		vector<int> stos;
		REP(j, n){
			while(ssize(stos) && wej[stos.back()][i] < wej[j][i]){
				int t = stos.back();
				if(t+1 <= j-1) pionowo[j-1][i].emplace_back(t+1);
				stos.pop_back();
			}
			if(ssize(stos)){
				int t = stos.back();
				if(t+1 <= j-1) pionowo[j-1][i].emplace_back(t+1);
				if(wej[t][i] == wej[j][i]) stos.pop_back();
			}
			stos.emplace_back(j);
		}
	}
	
	//~ REP(j, m) FOR(i, 0, j){
		//~ printf("%d %d: ", i, j);
		//~ for(int x : poziomo[i][j]) printf("%d ", x);
		//~ printf("\n");
	//~ }
	
	//~ REP(j, n) FOR(i, 0, j){
		//~ printf("%d %d: ", i, j);
		//~ for(int x : pionowo[i][j]) printf("%d ", x);
		//~ printf("\n");
	//~ }
	
	vector<int> jest(n, 0);
	
	ll wyn = 0ll;
	REP(j, m) FOR(i, 0, j){
		int maks_gora = 0, pop = -1;
		for(int dol : poziomo[i][j]){
			if(dol != pop+1) maks_gora = dol;
			pop = dol;
			
			FOR(poz, i, j) for(int &x : pionowo[dol][poz]){
				if(x < maks_gora) break;
				if(++jest[x] == j-i+1) ++wyn;
			}
			FOR(poz, i, j) for(int &x : pionowo[dol][poz]){
				if(x < maks_gora) break;
				jest[x] = 0;
			}
		}
	}
	return wyn;
}

• 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