Submission #1179280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179280		Gr1sen	Rectangles (IOI19_rect)	C++20	10 / 100	1 ms	328 KiB

rect

#include "rect.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

#define ll long long
#define vi vector<int>
#define vvi vector<vi>

ll count_rectangles(vector<vector<int>> B) {
	//cerr << "oink" << endl;
	if (B.size() <= 2 || B[0].size() <= 2) return 0;
	ll t = 0;
	vi L;
	for (int i = 0; i < B[0].size()-1; i++) {
		if (B[0][i] <= B[1][i] || B[2][i] <= B[1][i]) {
			L = {B[1][i]};
			continue;
		}
		while (L.size() && B[1][i] >= L.back()) L.pop_back();
		if (B[1][i+1] <= B[1][i]) {
			L.push_back(B[1][i]);
			continue;
		}
		auto a = lower_bound(L.rbegin(), L.rend(), B[1][i+1]);
		t += min((int)distance(L.rbegin(), a) + 1, (int)L.size());
		//cerr << distance(L.begin(), L.begin()) << " " << distance(L.begin(), L.end()) << endl;
		/*
		cerr << "new t : " << t << ", i : " << i << endl;
		cerr << "L : {";
		for (auto i : L) {
			cerr << i << ", ";
		}
		cerr << "}" << endl; //*/
		L.push_back(B[1][i]);
	}
	return t;
}

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