Submission #151633

#	Time	Username	Problem	Language	Result	Execution time	Memory
151633		shdut	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	376 ms	18404 KiB

cross

#include "cross.h"
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include <assert.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = b - 1; i >= a; i--)
#define ll long long
#define x first
#define y second
#define vi vector<int>
#define pii pair<int, int>
#define SZ(x) (int)(x.size())
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define inf 1000000007
#define DBG(x) cerr << (#x) << "=" << x << "\n";

#define N 100005

template<typename U, typename V> void Min(U &a, const V &b){if(a > b) a = b;}
template<typename U, typename V> void Max(U &a, const V &b){if(a < b) a = b;}
template<typename U, typename V> void add(U &a, const V &b){a = (a+b) % mod;}


ll sqr(int x){if(x <= 0)return 0; return 1LL * x * x;}
long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	int n = I.size();
	vector<pii> a(n);
	rep(i, 0, n)a[i] = {I[i], O[i]};
	sort(all(a));
	ll ans = 0;
	multiset<int>s;
	s.insert(inf);
	per(i, 0, n){
		if(s.size() == K){
			int x = min(*s.begin(), a[i].y);
			Max(ans, 1LL * a[i].x * a[i].x + 2LL * a[i].x * (x - a[i].x));
		}
		s.insert(a[i].y);
		if(s.size() > K)s.erase(s.begin());
	}
	s.clear();
	rep(i, 0, n)swap(a[i].x, a[i].y);
	sort(all(a));
	s.insert(inf);
	per(i, 0, n){
		if(s.size() == K){
			int x = min(*s.begin(), a[i].y);
			Max(ans, sqr(a[i].x) - sqr(a[i].x - x));
		}
		s.insert(a[i].y);
		if(s.size() > K)s.erase(s.begin());
	}
	return ans;
}

Compilation message (stderr)

cross.cpp: In function 'long long int SelectCross(int, std::vector<int>, std::vector<int>)':
cross.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(s.size() == K){
      ~~~~~~~~~^~~~
cross.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(s.size() > K)s.erase(s.begin());
      ~~~~~~~~~^~~
cross.cpp:59:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(s.size() == K){
      ~~~~~~~~~^~~~
cross.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(s.size() > K)s.erase(s.begin());
      ~~~~~~~~~^~~

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