Submission #149046

#	Time	Username	Problem	Language	Result	Execution time	Memory
149046		1 WA = 5 Push Up (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	119 ms	6888 KiB

cross

#include "cross.h"
#include <set>
#include <utility>
#include <algorithm>
#include <queue>
#define X first
#define Y second
using namespace std;
long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	int N = I.size();
	vector<pair<int,int> > V(N);
  for(int i = 0; i < N; i++){
    V[i] = {I[i], O[i]};
  }
  sort(V.begin(),V.end());
  long long mx = -1;
  priority_queue<int, vector<int>, less<int> > PQ1; // 큰 것 부터 튀어나옴
  priority_queue<int, vector<int>, greater<int> > PQ2; // 작은 것 부터 나감
  
  for(int i = N-1; i >= 0; i--){
    if(PQ2.size() < K) PQ2.push(V[i].Y);
    else{
      PQ1.push(V[i].Y);
      while(PQ1.top() > PQ2.top()){
        int v1 = PQ1.top();
        int v2 = PQ2.top();
        PQ1.pop();
        PQ2.pop();
        PQ1.push(v2);
        PQ2.push(v1);
      }
    }
    if(PQ2.size() < K) continue;
    mx = max(mx, 2ll*PQ2.top()*V[i].X - 1ll*V[i].X*V[i].X);
  }
  return mx;
}

Compilation message (stderr)

cross.cpp: In function 'long long int SelectCross(int, std::vector<int>, std::vector<int>)':
cross.cpp:21:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(PQ2.size() < K) PQ2.push(V[i].Y);
        ~~~~~~~~~~~^~~
cross.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(PQ2.size() < K) continue;
        ~~~~~~~~~~~^~~

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