Submission #809213

#	Time	Username	Problem	Language	Result	Execution time	Memory
809213		Username4132	Rectangles (IOI19_rect)	C++14	27 / 100	456 ms	1048576 KiB

rect

#include "rect.h"
#include<iostream>
#include<vector>
#include<bitset>
#include<cassert>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)
#define PB push_back


const int MAXN = 800;
bitset<MAXN> mask[MAXN][MAXN], moved[MAXN]; // column, start row
bitset<MAXN> one("1"), zero("0"), full;
int n, m, arr[MAXN][MAXN], brr[MAXN][MAXN];
int far[MAXN][MAXN][MAXN]; // row, l, r

void calc1(){
	dforn(row, n){
		forsn(i, 1, m-1){
			int mx = -1;
			forsn(j, i, m-1){
				mx = max(mx, arr[row][j]);
				if(mx<arr[row][i-1] && mx<arr[row][j+1]){
					far[row][i][j]=far[row+1][i][j];
				}
				else far[row][i][j]=row;
			}
		}
	}
}

void calc2(){
	forn(col, m){
		forsn(i, 1, n-1){
			int mx = -1;
			forsn(j, i, n-1){
				mx = max(mx, brr[col][j]);
				if(mx<brr[col][i-1] && mx<brr[col][j+1]){
					mask[i][col]|=(one<<j);
				}
			}
		}
	}
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	n=(int)a.size(), m=(int)a[0].size();
	assert(n<MAXN-4);
	assert(m<MAXN-4);
	forn(i, MAXN-4) full|=(one<<i);
	moved[MAXN-4]=full;
	dforn(i, MAXN-4) moved[i]=(moved[i+1]>>1);


	forn(i, n) forn(j, m) brr[j][i]=arr[i][j]=a[i][j];
	forn(i, m) forn(j, m) far[n][i][j]=n;

	calc1();
	calc2();

	ll ans=0;
	
	bitset<MAXN> bt, tmp;
	forsn(row, 1, n-1){
		forsn(i, 1, m-1){
			bt|=full;
			forsn(j, i, m-1){
				bt&=mask[row][j];
				tmp&=zero;
				tmp|=bt;
				tmp&=moved[far[row][i][j]];
				ans+=tmp.count();
			}
		}
	}
	
	return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28