Submission #148933

#	Time	Username	Problem	Language	Result	Execution time	Memory
148933		rkm0959 (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	360 ms	17644 KiB

cross

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional> // for less  

#define L long long

using namespace std;
using namespace __gnu_pbds;  

int n;

typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag,  
            tree_order_statistics_node_update>  
    ordered_set;  

ordered_set st;


L SelectCross(int K, vector<int>I, vector<int> O){
	L ret=0;	
	n=I.size();
	int i;
	vector<pair<int,int> >point;
	for(i=0;i<n;i++)
	{
		point.push_back(make_pair(O[i],I[i]));
	}
	sort(point.begin(),point.end(),[](pair<int,int>a, pair<int,int>b){
		return a.second<b.second;
	});
	for(i=n-1;i>=0;i--)
	{
		st.insert(point[i]);
		if(st.size()>=K)
		{
			L a=point[i].second;
			L b=st.find_by_order(st.size()-K)->first;
			//printf("%lld %lld %lld %lld\n",point[i].first,point[i].second,a,b);
			ret=max(ret,2*a*b-a*a);
		}
		else
		{
			//printf("%lld %lld\n",point[i].first,point[i].second);
		}
	}
	return ret;
}

Compilation message (stderr)

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

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