Submission #1215387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215387		brinton	Rectangles (IOI19_rect)	C++20	0 / 100	3 ms	584 KiB

rect

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

long long count_rectangles(vector<vector<int> > a) {
	int N = a[0].size();
	vector<int> bad(N,0);
	for(int i = 1;i < N-1;i++){
		if(a[1][i] < a[0][i] && a[1][i] < a[2][i]){
			bad[i] = false;
		}else{
			bad[i] = true;
		}
	}
	for(int i = 1;i < N;i++){
		bad[i] += bad[i-1];
	}
	// sparse table;
	int k = __lg(N)+1;
	vector<vector<int>> spt(k,vector<int>(N));
	spt[0] = a[1];
	for(int layer = 1;layer < k;layer++){
		for(int s = 0;s+(1 << layer)-1 < N;s++){
			spt[layer][s] = max(spt[layer-1][s],spt[layer-1][s+(1 << (layer-1))]);
		}
	}
	auto ask = [&](int l,int r){
		int len = r-l+1;
		int layer = __lg(len);
		return max(spt[layer][l],spt[layer][r-(1 << layer)+1]);
	};


	long long ans = 0;
	for(int l = 0;l < N;l++){
		int cmax = a[1][l+1];
		for(int r = l+2;r < N;r++){
			// int midmax = ask(l+1,r-1);
			int midmax = cmax;
			// cout << "(" << l << "," << r << "):" << midmax << "," << bad[r-1]-bad[l] << endl;
			if(midmax < a[1][l] && midmax < a[1][r] && bad[r-1]-bad[l] == 0){
				ans++;
			}
			cmax = max(cmax,a[1][r]);
		}
	}
	return ans;
}

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