Submission #149716

#	Time	Username	Problem	Language	Result	Execution time	Memory
149716		ProofByTLE (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	764 ms	33288 KiB

cross

#include "cross.h"

// Standard libraries
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <algorithm>

// Tree related
#include <functional>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

// Typedef
typedef long long lld;
typedef __gnu_pbds::tree<lld, __gnu_pbds::null_type, std::greater<lld>,
	__gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> orderstatset;

// Global order statistics tree
orderstatset ordertree;

// Add/remove element
void ordertree_add(lld d_out){
	if(ordertree.find(d_out) == ordertree.end()) ordertree.insert(d_out);
}
void ordertree_remove(lld d_out){
	if(ordertree.find(d_out) != ordertree.end()) ordertree.erase(d_out);
}

// Compress related
const lld compress_factor = 1e8;
std::map<lld, int> occurrence_count;
lld distuingish(lld x){
	occurrence_count[x]++;
	return x * compress_factor + occurrence_count[x];
}
lld undistuingish(lld x){return x / compress_factor;}

// Max
lld max2(lld a, lld b){return a>b ? a:b;}

// Main function. I = d_ins, O = d_outs
lld SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	
	// Sort d_InOut
	int N = I.size();
	std::vector<std::pair<lld, lld>> d_IO;
	for(int i=0; i<N; i++) d_IO.push_back({(lld)I[i], (lld)O[i]});
	std::sort(d_IO.begin(), d_IO.end());

	// Insert all outs
	std::vector<lld> added_outs(N, -1);
	for(int i=0; i<N; i++){
		added_outs[i] = distuingish(d_IO[i].second);
		ordertree_add(added_outs[i]);
	}

	// Search
	lld answer = -1;
	for(int i=0; i<N && ordertree.size() >= K; i++){

		lld this_Rin_min = d_IO[i].first;
		//printf("this_Rin_min = %lld, ", this_Rin_min);
		lld this_Rout_min = undistuingish(*ordertree.find_by_order(K-1));
		//printf("this_Rout = %lld\n", this_Rout_min);
		answer = max2(answer, this_Rin_min * (2 * this_Rout_min - this_Rin_min));

		// Remove current point
		ordertree_remove(added_outs[i]);
	}

	return answer;
}

Compilation message (stderr)

cross.cpp: In function 'lld SelectCross(int, std::vector<int>, std::vector<int>)':
cross.cpp:61:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<N && ordertree.size() >= K; i++){
                      ~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 8 / 8
• Subtask 2: 55 / 55
• Subtask 3: 37 / 37