oj.uz

Submission #149716

# Submission time Handle Problem Language Result Execution time Memory
149716 2019-09-01T07:00:56 Z ProofByTLE(#3614, Mahotsukai, McDic, Redux) Crosses on the Grid (FXCUP4_cross) C++17
100 / 100
 764 ms 33288 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 29 ms 2428 KB Output is correct
6 Correct 728 ms 33248 KB Output is correct
7 Correct 650 ms 33248 KB Output is correct
8 Correct 672 ms 33240 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 29 ms 2428 KB Output is correct
6 Correct 728 ms 33248 KB Output is correct
7 Correct 650 ms 33248 KB Output is correct
8 Correct 672 ms 33240 KB Output is correct
9 Correct 5 ms 128 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 28 ms 2428 KB Output is correct
13 Correct 282 ms 17128 KB Output is correct
14 Correct 670 ms 33244 KB Output is correct
15 Correct 705 ms 33240 KB Output is correct
16 Correct 634 ms 33248 KB Output is correct

Subtask #3
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 29 ms 2428 KB Output is correct
6 Correct 728 ms 33248 KB Output is correct
7 Correct 650 ms 33248 KB Output is correct
8 Correct 672 ms 33240 KB Output is correct
9 Correct 5 ms 128 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 28 ms 2428 KB Output is correct
13 Correct 282 ms 17128 KB Output is correct
14 Correct 670 ms 33244 KB Output is correct
15 Correct 705 ms 33240 KB Output is correct
16 Correct 634 ms 33248 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 6 ms 512 KB Output is correct
19 Correct 23 ms 2420 KB Output is correct
20 Correct 285 ms 17128 KB Output is correct
21 Correct 505 ms 26336 KB Output is correct
22 Correct 678 ms 33248 KB Output is correct
23 Correct 655 ms 33252 KB Output is correct
24 Correct 764 ms 33248 KB Output is correct
25 Correct 635 ms 33248 KB Output is correct
26 Correct 537 ms 33288 KB Output is correct