Submission #149051

#	Time	Username	Problem	Language	Result	Execution time	Memory
149051		Seishun Buta Yarou wa Yumemiru Shoujo no Yume wo Minai (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	357 ms	19180 KiB

cross

#include "cross.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

long long SelectCross(int K, std::vector<int> I, std::vector<int> O) 
{
	vector<ii> vec;
	int n=I.size();
	for(int i=0;i<n;i++)
	{
		vec.pb({O[i],I[i]});
	}
	sort(vec.begin(),vec.end());
	reverse(vec.begin(),vec.end());
	ll ans = 0;
	pbds T;
	int timer=-1;
	for(int i=0;i<n;i++)
	{
		ll grid = vec[i].fi; 
		if(T.size()>=K-1)
		{
			ll vv = ll(1e18);
			if(K-2>=0) vv=-(*T.find_by_order(K-2)).fi;
			ll lowpt = min(vec[i].se, vv);
			ans = max(ans, grid*grid-(grid-lowpt)*(grid-lowpt));
		}
		T.insert({-vec[i].se,++timer});
	}
	return ans;
}

Compilation message (stderr)

cross.cpp: In function 'long long int SelectCross(int, std::vector<int>, std::vector<int>)':
cross.cpp:37:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(T.size()>=K-1)
      ~~~~~~~~^~~~~

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